Decode USB packets

Question 1

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

Question 2

Sandbox

Question 3

Bounty for the answer that will run on his 6502 breadboard computer. :)

Question 4

do test cases say that initial J isn't present in the input?

Question 5

@NooneAtAll correct; the intial J is not part of the input

Question 6

@640KB which 6502 platform are we supposed to target? I want to try using this emulator.

Question 7

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.

enter image description here

Question 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)

Question 9

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)!

Question 10

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

Question 11

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.

Question 12

i guess the they functions are not assigned to a variable

Question 13

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
))

Question 14

Nice. I got 68 bytes without regex, but then realised it's almost the same as your before-change-of-approach version...

Question 15

@DominicvanEssen nice golf of the rle approach!

Question 16

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

Question 17

J, 26 bytes

Takes in JK as 0 1.

t#~0=_6|.(61ドル)E.t=:2=/0,円]

Try it online!

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

Question 18

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.

Question 19

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

Question 20

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

Question 21

int can be shortened to +.

Question 22

@ovs thanks for the tip

Question 23

for .. in qualifies as generator expression, so you can drop one pair of parenthesis and save two more bytes.

Question 24

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.

Question 25

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

Question 26

-1 byte by replacing ø€Ë with üQ.

Question 27

@KevinCruijssen Thanks!

Question 28

Charcoal, 19 bytes

⪫⪪⭆θ=×ばつ16

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
 6 Literal `6`
 + Concatenated with
 0 Literal string `0`
⪫ Join with
 1 Literal string `1`
 ×ばつ Repeated
 6 Literal `6`
 Implicitly print

Question 29

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.

Question 30

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 *'|')

Question 31

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

Question 32

The second one doesn't work: /1{6}0/ needs to be adapted to true and false

Question 33

61: Try it online!

Question 34

@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.

Question 35

By modifying pxeger's version to take an array, 59 bytes

Question 36

@Ausername Thanks, but I'd like to keep it with the string version. Feel free to post yours as an answer

Question 37

Jelly, 14 bytes

Ż=×ばつ‘ʋ7Ƒ?ɼƇ

Try it online!

Takes J and K as 0 and 1.

Question 38

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.

Question 39

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.

xash 11.3k1 gold badge15 silver badges39 bronze badges · Accepted Answer · 2021-06-10 11:08:51Z

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.

enter image description here

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

Sign up or log in

Post as a guest

Post as a guest

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

Post as a guest

Linked

Related

Hot Network Questions

convey, ³¹ 25 bytes