Decode USB packets

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.

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 , so the shortest code in bytes wins
• Sandbox Jun 10 at 7:16
• Bounty for the answer that will run on his 6502 breadboard computer. :) Jun 10 at 13:44
• do test cases say that initial J isn't present in the input? Jun 11 at 18:25
• @NooneAtAll correct; the intial J is not part of the input Jun 11 at 19:14
• @640KB which 6502 platform are we supposed to target? I want to try using this emulator. Jun 15 at 8:14

convey, 31 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.

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)

• 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)! Jun 11 at 23:06

MATL, 15 14 bytes

0ihd~126B63BZt


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

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


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.

• i guess the they functions are not assigned to a variable Jun 10 at 15:54

R, 8376 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
))

• Nice. I got 68 bytes without regex, but then realised it's almost the same as your before-change-of-approach version... Jun 10 at 23:53
• @DominicvanEssen nice golf of the rle approach! Jun 11 at 5:56

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

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  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. 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 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 • int can be shortened to +. – ovs Jun 10 at 11:32 • @ovs thanks for the tip Jun 10 at 11:34 • for .. in qualifies as generator expression, so you can drop one pair of parenthesis and save two more bytes. Aug 9 at 23:05 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. 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  • -1 byte by replacing ø€Ë with üQ. Aug 5 at 7:33 • @KevinCruijssen Thanks! Aug 6 at 19:44 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  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. K (ngn/k), 24 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 *'|') 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 • The second one doesn't work: /1{6}0/ needs to be adapted to true and false Jun 10 at 8:21 • Jun 10 at 8:47 • @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. – user100690 Jun 10 at 8:49 • By modifying pxeger's version to take an array, 59 bytes Jun 10 at 8:50 • @Ausername Thanks, but I'd like to keep it with the string version. Feel free to post yours as an answer – user100690 Jun 10 at 8:51 Jelly, 14 bytes Ż⁼Ɲ0ȯ1×‘ʋ7Ƒ?ɼƇ  Try it online! Takes J and K as 0 and 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.

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.