Decode USB packets

Question

Inspired by this video by Ben Eater. This challenge forms a pair with Encode USB packets.

The USB 2.0 protocol uses, at a low level, a line code called non-return-to-zero encoding (specifically, a variant called NRZI), in which a stream of bits is encoded into a stream of two electrical level states J and K. Decoding works as follows:

Start with some initial state, which is either J or K
For each state to be decoded:
- If the state is different to the previous state, write a 0.
- If the state is the same as the previous state, write a 1.

For this challenge, we will assume the encoding starts in state J.

However, it's not that simple: an additional process called bit stuffing takes place, which is designed to make it easier to detect if the signal has dropped out. After 6 consecutive 1 bits are written, a meaningless 0 bit is written to ensure the signal never stays in the same state (J or K) for too long. When decoding, you need to take this into account and remove the 0 bit that necessarily occurs after 6 consecutive 1s.

The full USB specification is available here on the USB website, or mirrored (and easier to access) here, but I'd caution you before reading it because it's extremely long and the pertinent information is hard to pin down.

Task

Given a non-empty list of Js or K states as input, decode the string using the USB implementation of NRZI described above, and output a binary string.

You may assume the input will never contain invalid data with incorrect bit stuffing (i.e., it will never contain 7 consecutive 1s).

Test-cases

Input              Output
=====================================
J                  1
K                  0
JKJKKJJ            1000101
KJKJKJKJ           00000000
JJJJJJKKK          11111111
KJJJJJJKJ          001111100
KJJJJJJJKJK        0011111100
KJJJJJJJKKJK       00111111100
KJJJJJJJKKKKKKKJKJ 0011111111111100
KJJJJJJJJKJ        (incorrect bit stuffing; does not need to be handled)
KJJJKKKJKJJJJKJJ   0011011000111001
KKKJJKJKJJJJKKJKJJJJKKJKJJJJKJKJKKKKJKKKJKKKKJJKJKKJJJJJKJJKKKKKJJJJKKKKJJJJKKKKJJJJKKKKJKKJJJJKJJJJJKJJKKKJJJJJKKKKJJKKJJJJKKJKJJJJKKJJKKKJKJJKJJJKJJKKJKKJJJJKJJJKJKKKJJJKKKKKJJJKKKJJKJJKKKKKJJJJKKKKJJJKJKJJKKKKJJKJKKKJKJJJKKKJJKJKJKKKKKKKJKKKKJJJKJKKKKKJJKKKJKKJKJJKKJKJJKKKKJJJJKJJJKKJKJJJJKKKKJKKKKJKKJJKKJJJJKKKJKKKKJJKKKJKJKKKJKJJJKKJJKJKK   01101000011101000111010001110000011100110011101000101111001011110111011101110111011101110010111001111001011011110111010101110100011101010110001001100101001011100110001101101111011011010010111101110111011000010111010001100011011010000011111101110110001111010110010001010001011101110011010001110111001110010101011101100111010110000110001101010001

Rules

The input should be a string or array, with the two states J and K being represented by two distinct values of your choice (within reason)
The output should be a string or array of 1s and 0s or of trues and falses
You may use any standard I/O method
Standard loopholes are forbidden
This is code-golf, so the shortest code in bytes wins

Bounty for the answer that will run on his 6502 breadboard computer. :) — 640KB, Commented Jun 10, 2021 at 13:44
do test cases say that initial J isn't present in the input? — Noone AtAll, Commented Jun 11, 2021 at 18:25
@640KB which 6502 platform are we supposed to target? I want to try using this emulator. — Razetime, Commented Jun 15, 2021 at 8:14

xash · Accepted Answer · 2021-06-10 11:31:26Z

12

+200

convey, ³¹ 25 bytes

Takes JK as 01.

>="*>0
",v+<"(6
{0>">>!`}

Try it online!

Compares = the string with itself with a J prepended ,0. The middle loop just adds the comparisons to a counter (starting with 0) that gets reset on a 0. Only take ! elements where the previous counter was less than 6 (6.

edited Jun 10, 2021 at 11:31

answered Jun 10, 2021 at 11:08

xash

11.3k1 gold badge14 silver badges39 bronze badges

Add a comment |

Razetime · Accepted Answer · 2021-06-10 14:31:25Z

8

Husk, 11 bytes

σḋ126ḋ63Ẋ=Θ

Try it online!

Takes an array of bits(0=J, 1=K), outputs an array of bits(formatted as string for convenience)

Explanation

σḋ126ḋ63Ẋ=Θ
          Θ Prepend 0
        Ẋ=  map overlapping pairs by equality
σḋ126ḋ63    replace binary digits of 126 with binary digits of 63 (stolen from Luis Mendo)

edited Jun 10, 2021 at 14:31

answered Jun 10, 2021 at 14:22

Razetime

27.4k3 gold badges29 silver badges72 bronze badges

2

\$\begingroup\$ This is funny: I just answered the 'encode USB' challenge in Husk, and thought I'd come here to do it the other way around... only to find that you've already beaten me to it with almost exactly the same approach (and same bytes)! \$\endgroup\$
– Dominic van Essen
Commented Jun 11, 2021 at 23:06

Add a comment |

Luis Mendo · Accepted Answer · 2021-06-10 09:43:12Z

MATL, 15 14 bytes

0ihd~126B63BZt

Input is an array with 0 for 'J' and 1 for 'K'.

Try it online! Or verify all test cases.

Explanation

0       % Push 0
i       % Input: string
h       % Concatenate
d       % Consecutive differences
~       % Negate: converts nonzero to 0, and zero to 1. Gives a numeric vector (*)
126B    % Push 126, convert to binary. Gives [1 1 1 1 1 1 0]
63B     % Push 63, convert to binary. Gives [1 1 1 1 1 1]
Zt      % String replace (works for numeric vectors too). Replaces [1 1 1 1 1 1 0]
        % by [1 1 1 1 1 1] in (*)
        % Implicit display

tsh · Accepted Answer · 2021-06-10 10:34:29Z

4

JavaScript (ES6), 54 bytes

s=>s.replace(/./g,a=>s^(s=a>"J")?i=i>5?'':0:++i/i,i=0)

Try it online!

Take input as a string of "J" / "K". Output a string with "0" and "1".

And f=J=>J.replace(/./g,a=>J^(J=a>f)?i=i>5?'':0:++i/i,i=0) is 54 bytes too.

JavaScript (ES6), 44 bytes

s=>s.flatMap(a=>s^(s=a)?i=i>5&&[]:++i>0,i=0)

Try it online!

Take input as an array of false (for "J") and true (for "K"). Output an array of false and true.

edited Jun 10, 2021 at 10:34

answered Jun 10, 2021 at 8:50

tsh

35k2 gold badges33 silver badges128 bronze badges

\$\begingroup\$ i guess the they functions are not assigned to a variable \$\endgroup\$
– Drdilyor
Commented Jun 10, 2021 at 15:54

Add a comment |

pajonk · Accepted Answer · 2021-06-10 18:51:59Z

4

R, 83 76 62 bytes

function(x)gsub('(1{6})0','\\1',Reduce(paste0,+!diff(c(0,x))))

Try it online!

Takes input as 0(J) and 1(K).

Outputs string of 1s and 0s.

Change of approach after looking at @Luis Mendo's answer.

function(x)    # function taking x as input
gsub(          # replace all occurences of
'(1{6})0',     # 6 ones and a zero
'\\1',         # with just 6 ones (first capturing group)
Reduce(paste0, # in a following vector collapsed to string
+!diff(c(0,x)) # negated differences of x with 0 prepended 
               # converted from logical to numeric with unary +
               # this would be the output without bit stuffing
))

edited Jun 10, 2021 at 18:51

answered Jun 10, 2021 at 9:04

pajonk

17.8k3 gold badges25 silver badges74 bronze badges

1

\$\begingroup\$ Nice. I got 68 bytes without regex, but then realised it's almost the same as your before-change-of-approach version... \$\endgroup\$
– Dominic van Essen
Commented Jun 10, 2021 at 23:53
\$\begingroup\$ @DominicvanEssen nice golf of the rle approach! \$\endgroup\$
– pajonk
Commented Jun 11, 2021 at 5:56

Add a comment |

a stone arachnid · Accepted Answer · 2021-06-12 18:59:32Z

4

C (gcc), 79 76 bytes

-3 thanks to @ceilingcat

x;c;a(char*p){x=74;for(c=1;c*=*p==x,x=*p++;c=c>5?x=*p++,1:c+1)putchar(!!c);}

Try it online! Takes input as J and K, outputs with bytes 0x00 and 0x01 for 0 and 1.

For output as numeric 0 and 1, Try it online! for 78 bytes.

Encoder

edited Jun 12, 2021 at 18:59

answered Jun 12, 2021 at 12:56

a stone arachnid

3,22013 silver badges21 bronze badges

Add a comment |

xash · Accepted Answer · 2021-06-10 08:14:03Z

3

J, 26 bytes

Takes in JK as 0 1.

t#~0=_6|.(6$1)E.t=:2=/\0,]

Try it online!

t#~0=_6|.(6$1)E.t=:2=/\0,]
                       0,] prepend a J
                   2=/\    pair-wise equal
                t=:        store as t
         (6$1)E.           bitmask of places where 6 ones starts
     _6|.                  shifted by 6 bits
   0=                      negate
t#~                        take only truthy bits from t

answered Jun 10, 2021 at 8:14

xash

11.3k1 gold badge14 silver badges39 bronze badges

Add a comment |

emanresu A · Accepted Answer · 2021-06-10 09:32:00Z

Vyxal, 16 bytes

1p-Ṫv¬ṅ\16*:0+$V

Try it Online!

1p               # Prepend a 1
  -              # Differences - truthy if unchanged, falsy if changed
   Ṫ             # Get rid of last
    v¬           # Vectorised not
      ṅ          # Joined
       \16*      # Six ones
           :     # Duplicate
            0+   # Append a 0 to the first
              $  # Swap
               V # Replace

Takes the difference of the list with a 1 prepended and the list itself, NOTted, to get the values. Then spend the remaining 10 bytes on doing the bit stuffing.

Kaddath · Accepted Answer · 2021-06-10 09:46:40Z

3

PHP -F, 96 bytes

for($s=$r=$argn;$s[++$i]!='';)$r[$i]=+!abs($s[$i]-$s[$i-1]);echo str_replace(1111110,111111,$r);

Try it online!

Well, I.. tried.. to make it short.. hum!

takes a string of 0 (J) and 1 (K) as input

answered Jun 10, 2021 at 9:46

Kaddath

2,9074 silver badges9 bronze badges

Add a comment |

Wasif · Accepted Answer · 2021-06-10 11:33:59Z

3

Python 2, 77 bytes

lambda s:''.join((`+(x==y)`for x,y in zip('J'+s,s))).replace('1'*6+'0','1'*6)

Try it online!

-2 bytes thanks to @ovs

edited Jun 10, 2021 at 11:33

answered Jun 10, 2021 at 11:23

Wasif

12.3k1 gold badge17 silver badges47 bronze badges

2

\$\begingroup\$ int can be shortened to +. \$\endgroup\$
– ovs
Commented Jun 10, 2021 at 11:32
\$\begingroup\$ @ovs thanks for the tip \$\endgroup\$
– Wasif
Commented Jun 10, 2021 at 11:34
\$\begingroup\$ for .. in qualifies as generator expression, so you can drop one pair of parenthesis and save two more bytes. \$\endgroup\$
– movatica
Commented Aug 9, 2021 at 23:05

Add a comment |

Kirill L. · Accepted Answer · 2021-06-12 21:41:28Z

3

Red, 79 bytes

func[x][p: s: 0 collect[foreach i x[s: any[all[s < 6 keep p = i s + 1]0]p: i]]]

Try it online!

Takes input as a block of \$1\$s and \$0\$s, outputs a block of booleans.

Test suite on TIO uses two additional transformation functions that allow reading inputs from JK-strings as in task specification and convert output to numbers for nicer visualization.

answered Jun 12, 2021 at 21:41

Kirill L.

14.1k2 gold badges16 silver badges50 bronze badges

Add a comment |

Makonede · Accepted Answer · 2021-08-06 19:47:14Z

3

05AB1E, 13 12 bytes

-1 thanks to Kevin Cruijssen.

0ìüQJƵPbD¨.:

Try it online! Uses 0 for J and 1 for K.

0ìüQJƵPbD¨.:  # full program
          .:  # replace all instances of...
     ƵP       # 126...
       b      # in binary...
          .:  # in...
    J         # joined...
  ü           # are all digits of each element in...
0             # literal...
 ì            # concatenated with...
              # implicit input...
   Q          # equal...
          .:  # with...
      ƵP      # 126...
        bD    # in binary...
          ¨   # excluding the last digit
              # implicit output

edited Aug 6, 2021 at 19:47

answered Jun 10, 2021 at 21:44

Makonede

6,52019 silver badges49 bronze badges

1

\$\begingroup\$ -1 byte by replacing ø€Ë with üQ. \$\endgroup\$
– Kevin Cruijssen
Commented Aug 5, 2021 at 7:33
\$\begingroup\$ @KevinCruijssen Thanks! \$\endgroup\$
– Makonede
Commented Aug 6, 2021 at 19:44

Add a comment |

Neil · Accepted Answer · 2021-06-10 11:52:52Z

Charcoal, 19 bytes

⪫⪪⭆θ⁼ι§⁺Jθκ⁺×1⁶0×1⁶

Try it online! Link is to verbose version of code. Explanation:

   θ                Input string
  ⭆                 Map over characters and join
        J           Literal string `J`
       ⁺            Concatenated with
         θ          Input string
      §             Indexed by
          κ         Current index
    ⁼               Equals
     ι              Current character
 ⪪                  Split on
             1      Literal string `1`
            ×       Repeated
              ⁶     Literal `6`
           ⁺        Concatenated with
               0    Literal string `0`
⪫                   Join with
                 1  Literal string `1`
                ×   Repeated
                  ⁶ Literal `6`
                    Implicitly print

Razetime · Accepted Answer · 2021-06-10 14:16:56Z

2

Stax, 16 bytes

Å3≈àE∩◄σ←π<δô╝ìà

Run and debug it

takes in a string/array of bytes 0x00 for J and 0x01 for K.

Outputs a string, same as the given testcases.

Sadly, this 14 byte program doesn't work since stax auto-replaces null bytes with spaces.

answered Jun 10, 2021 at 14:16

Razetime

27.4k3 gold badges29 silver badges72 bronze badges

Add a comment |

ngn · Accepted Answer · 2021-11-30 10:53:05Z

2

K (ngn/k), 25 bytes

*|+(126=2/')_7':(&6),0=':

Try it online!

Takes J as 0, and K as 1. Returns a list of 0s and 1s.

0=': run an equals-each-prior, seeded with 0 on the (implicit) input, handling the non-return-to-zero part
7':(&6), prepend 6 0s to the input, then slice into length-7 sliding windows. the first 6 slices will contain some dummy 0s
(126=2/')_ drop chunks of 1 1 1 1 1 1 0, i.e. where the last value in the chunk is a dummy 0 inserted for bit stuffing purposes
*|+ return the last value of each chunk (saves a byte over *'|')

edited Nov 30, 2021 at 10:53

ngn

15.3k2 gold badges43 silver badges87 bronze badges

answered Jun 10, 2021 at 20:01

coltim

6,0235 silver badges13 bronze badges

Add a comment |

score 1 · Accepted Answer · 2021-06-10 08:50:16Z

1

JavaScript (Node.js), 61 bytes

n=>n.replace(/./g,(e,i)=>1-e^n[i-1]).replace(/1{6}0/g,111111)

Try it online!

I have tried to make sure it outputs numbers.

-10 bytes by pxeger

edited Jun 10, 2021 at 8:50

answered Jun 10, 2021 at 8:01

user100690

\$\begingroup\$ The second one doesn't work: /1{6}0/ needs to be adapted to true and false \$\endgroup\$
– pxeger
Commented Jun 10, 2021 at 8:21
\$\begingroup\$ 61: Try it online! \$\endgroup\$
– pxeger
Commented Jun 10, 2021 at 8:47
\$\begingroup\$ @pxeger First comment: the second one was not the final solution, just a remark, so I will remove that. Second comment: I'll edit that into the answer. \$\endgroup\$
– user100690
Commented Jun 10, 2021 at 8:49
\$\begingroup\$ By modifying pxeger's version to take an array, 59 bytes \$\endgroup\$
– emanresu A
Commented Jun 10, 2021 at 8:50
\$\begingroup\$ @Ausername Thanks, but I'd like to keep it with the string version. Feel free to post yours as an answer \$\endgroup\$
– user100690
Commented Jun 10, 2021 at 8:51

Add a comment |

xigoi · Accepted Answer · 2021-06-10 09:15:26Z

1

Jelly, 14 bytes

Ż⁼Ɲ0ȯ1×‘ʋ7Ƒ?ɼƇ

Try it online!

Takes J and K as 0 and 1.

answered Jun 10, 2021 at 9:15

xigoi

7,3312 gold badges12 silver badges23 bronze badges

Add a comment |

Neil · Accepted Answer · 2021-06-10 10:23:16Z

1

Retina 0.8.2, 31 bytes

(.)(?<=(\1.|^J)?)
$#2
1{6}0
6$*

Try it online! Link includes test cases. Explanation:

(.)(?<=(\1.|^J)?)

For each letter, look behind for a possible duplicate or a leading J.

$#2

If it was then replace it with a 1 otherwise replace it with a 0.

1{6}0
6$*

Remove the 0 that appears after a run of six 1s.

answered Jun 10, 2021 at 10:23

Neil

174k12 gold badges73 silver badges277 bronze badges

Add a comment |

Nick Kennedy · Accepted Answer · 2021-06-10 21:02:24Z

1

Jelly, 14 bytes

ŻI¬“~?‘B¤œṣjƭƒ

Try it online!

A monadic link taking the argument as a vector of 0 (=J) and 1 (=K) and returning a vector of 0 and 1.

answered Jun 10, 2021 at 21:02

Nick Kennedy

21.2k3 gold badges17 silver badges43 bronze badges

Add a comment |

Stack Exchange Network

Decode USB packets

Task

Test-cases

Rules

19 Answers 19

convey, ³¹ 25 bytes

Husk, 11 bytes

Explanation

MATL, 15 14 bytes

Explanation

JavaScript (ES6), 54 bytes

JavaScript (ES6), 44 bytes

R, 83 76 62 bytes

C (gcc), 79 76 bytes

J, 26 bytes

Vyxal, 16 bytes

PHP -F, 96 bytes

Python 2, 77 bytes

Red, 79 bytes

05AB1E, 13 12 bytes

Charcoal, 19 bytes

Stax, 16 bytes

K (ngn/k), 25 bytes

JavaScript (Node.js), 61 bytes

Jelly, 14 bytes

Retina 0.8.2, 31 bytes

Jelly, 14 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
binary
encoding
or ask your own question.

Linked

Hot Network Questions

Decode USB packets

Task

Test-cases

Rules

19 Answers 19

convey, 31 25 bytes

Husk, 11 bytes

Explanation

MATL, 15 14 bytes

Explanation

JavaScript (ES6), 54 bytes

JavaScript (ES6), 44 bytes

R, 83 76 62 bytes

C (gcc), 79 76 bytes

J, 26 bytes

Vyxal, 16 bytes

PHP -F, 96 bytes

Python 2, 77 bytes

Red, 79 bytes

05AB1E, 13 12 bytes

Charcoal, 19 bytes

Stax, 16 bytes

K (ngn/k), 25 bytes

JavaScript (Node.js), 61 bytes

Jelly, 14 bytes

Retina 0.8.2, 31 bytes

Jelly, 14 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfbinaryencoding or ask your own question.

Linked

Related

Hot Network Questions

convey, ³¹ 25 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
binary
encoding
or ask your own question.