Encode USB packets (part 2)

Question

Inspired by this video by Ben Eater. This challenge forms a pair with Decode 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. Encoding works as follows:

• Start with some initial state, which is either J or K
• For each bit to be encoded:
  • If the bit is a 0, switch the state from J to K or from K to J
  • If the bit is a 1, maintain the same state as before
  • and output that state

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 1s are read, an extra meaningless 0 bit is processed to ensure the signal never stays in the same state (J or K) for too long.

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 binary string as input, encode the string using the USB implementation of NRZI described above, and output a string of Js or Ks.

Test-cases

Input              Output
=====================================
1                  J
0                  K
1000101            JKJKKJJ
00000000           KJKJKJKJ
11111111           JJJJJJKKK
001111100          KJJJJJJKJ
0011111100         KJJJJJJJKJK
00111111100        KJJJJJJJKKJK
0011111111111100   KJJJJJJJKKKKKKKJKJ
0011011000111001   KJJJKKKJKJJJJKJJ
01101000011101000111010001110000011100110011101000101111001011110111011101110111011101110010111001111001011011110111010101110100011101010110001001100101001011100110001101101111011011010010111101110111011000010111010001100011011010000011111101110110001111010110010001010001011101110011010001110111001110010101011101100111010110000110001101010001   KKKJJKJKJJJJKKJKJJJJKKJKJJJJKJKJKKKKJKKKJKKKKJJKJKKJJJJJKJJKKKKKJJJJKKKKJJJJKKKKJJJJKKKKJKKJJJJKJJJJJKJJKKKJJJJJKKKKJJKKJJJJKKJKJJJJKKJJKKKJKJJKJJJKJJKKJKKJJJJKJJJKJKKKJJJKKKKKJJJKKKJJKJJKKKKKJJJJKKKKJJJKJKJJKKKKJJKJKKKJKJJJKKKJJKJKJKKKKKKKJKKKKJJJKJKKKKKJJKKKJKKJKJJKKJKJJKKKKJJJJKJJJKKJKJJJJKKKKJKKKKJKKJJKKJJJJKKKJKKKKJJKKKJKJKKKJKJJJKKJJKJKK

Rules

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

Answer 1

Husk, 11 bytes

G=Jḋ126xḋ63

Try it online!

Input as array of 0s and 1s, output as array of 1s (for state J) and 0s (for state K): TIO header converts to Js and Ks.

       x    # split input on
        ḋ63 # binary digits of 63 = [1,1,1,1,1,1]
  J         # then join back together using
   ḋ126     # binary digits of 126 = [1,1,1,1,1,1,0]
G=          # and scan from the left by equality

Answer 2

JavaScript (ES6), 53 bytes

Expects a binary string. Returns an array of 0's and 1's.

s=>[...s.replace(/1{6}/g,'$&0')].map(q=c=>q^=c^!!++q)

Try it online!

Commented

This is a rather straightforward implementation in two steps.

s =>           // s = input string

               // STEP 1 - Bit stuffing
               //
[...s.replace( // replace in s:
  /1{6}/g,     //   each group of six consecutive 1's
  '$&0'        //   with the same group with a trailing 0
)]             // split the resulting string

               // STEP 2 - NRZI encoding
               //
.map(q =       // initialize q to a zero'ish, non-numeric value
  c =>         // for each character c:
  q ^=         //   invert q if ...
    c ^        //     ... c is not equal to the result of
    !!++q      //     the test 'q is a number'
               //     (0 on the 1st iteration, 1 afterwards)
)              // end of map()

Answer 3

Jelly, 12 bytes

7Ṭ¬©Ṗœṣ@j®⁼\

A monadic Link that accepts a list of integers (from \$[0,1]\$) and yields a list of integers (from \$[0,1]\$) where \$0\$ represents \$K\$.

Try it online! Or see the test-suite.

How?

7Ṭ¬©Ṗœṣ@j®⁼\ - Link: list of integers in [0..1], A
7            - seven
 Ṭ           - untruth -> [0,0,0,0,0,0,1]
  ¬          - logical NOT -> [1,1,1,1,1,1,0]
   ©         - copy to register
    Ṗ        - pop -> [1,1,1,1,1,1]
     œṣ@     - (A) split on sublists equal to (that)
         ®   - recall from register
        j    - (split list) join (register value)
           \ - cumulative reduce with:
          ⁼  -   (left) equals (right)?

---

11 if we could take input with 0 meaning true and 1 meaning false with 7Ṭ©Ṗœṣ@j®⁻\.

Answer 4

convey, 31 bytes

Outputs KJ as 01.

v|6
0"("=0
+*6!<}
""~,="
{ 5 1<

Try it online!

In the top left is a counter that gets incremented by the input 1s + and reset whenever it reaches 6 |6 or the input has a 0 *. If it reaches 6, it also injects a 0 into the stream (the ("=0 6!< part). Because the input stream would be faster (the 0 would get there 2 bits too late), we delay it by 5 ticks ~5. On the bottom right is the current output bit that gets flipped on 0s with = and then copied into the output =}.

Answer 5

R, 59 bytes

function(x)cumsum(49-utf8ToInt(gsub('(1{6})','\\10',x)))%%2

Try it online!

Regex-based bit-stuffing stolen from inspired by pajonk's R answer to the paired usb-decoding challenge.

The state-switching is achieved here by determining whether the cumulative sum is odd or even.

Answer 6

Vyxal, 16 bytes

\16*:0+V1$(nɽ߬…

Try it Online!

\16*             # Six ones
    :0+          # Duplicate and append a 0
       V         # Replace in input
        1$       # Starting with a one
          (      # Iterating through the string
             ߬  # Flip if...
           nɽ    # It's a 1
               … # Print without popping

Returns 1 for J and 0 for K. Here's a version that does JKs.

Answer 7

Jelly, 14 bytes

“?~‘Bœṣjƭƒ^¬¥\

Try it online!

-2 bytes thanks to Nick Kennedy

“?~‘Bœṣjƭƒ^¬¥\  Main Link; accepts a list of [0, 1] on the left
“?~‘            63, 126
    B           To binary ([1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 0])
         ƒ      Reduce starting with the input:
        ƭ       Tie; cycle
     œṣ         The first time, split on sublist ([1, 1, 1, 1, 1, 1])
       j        The second time, join on [1, 1, 1, 1, 1, 1, 0]
             \  Cumulative reduce
          ^´   Each time, XOR, and then logical NOT

Answer 8

<>^v, 161 bytes

1±n"0"o"1"i0q.h"J"j"K"kJtv
v   v=ICc®NHn)N  v=N-?1¿H<
    >Q)7=v_qv    >`!     ~
 vcOn(Nq0<  v    >Ktv    T
v<          <>TJ=^Jtv    ^
>C         O=^      >    ^

Explanation

First line

1±n"0"o"1"i0q.h"J"j"K"kJtv

1                          Push 1 to stack
 ±                         Negate
  n                        Store in variable `n`
   "0"                     Push "0"
      o                    Store in variable `o`
       "1"                 Push "1"
          i                Store in variable `i`
           0               Push 0
            q              Store in variable `q`
             .             Read line from stdin
              h            Store in variable `h`
               "J"         Push "J"
                  j        Store in variable `j`
                   "K"     Push "K"
                      k    Store in variable `k`
                       J   Push value of variable `j` ("J")
                        t  Store in variable `t`
                         v Redirect instruction pointer down

The variables i and o store the values "1" and "0"", j and k store "J" and "K". h contains the line read from stdin (1's and 0's). q, initialized to 0, will be used for bit stuffing. n is the "current character pointer".

The main loop

v   v=ICc®NHn)N  v=N-?1¿H< <-- loop starts here
    >Q)7=v_qv    >`!     ~
 vcOn(Nq0<  v    >Ktv    T
v<          <>TJ=^Jtv    ^
>C         O=^      >    ^
[start of loop]
<    Send instruction pointer leftward
H    Push value of variable `h` to stack
¿    Push length of top of stack
1    Push 1
?    Swap top two elements
-    Substract second element of stack to top of stack
N    Push value of variable `n`
=    If the top two elements of the stack (length of `h` - 1 and `n`) are equal (reached end of string)
    v    Send instruction pointer down
    >    Send instruction pointer right 
    `    Print newline
    !    Exit
N    Push value of variable `n` (character index in string)
)    Increment top of stack (increment character index in string)
n    Pop and write to variable `n`
H    Push value of variable `h` (string that was previously read from stdin and that contains the 0's and 1's
N    Push value of variable `n`
®    Set top of stack to (second element of stack)[top of stack] (character read)
c    Write to variable `c` ("current")
C    Push value of variable `c` (variable write pops the stack)
I    Push value of variable `i` ("1")
=    If the top two elements of the stack (current character and "1") are equal
    v    Send instruction pointer down
    >    Send instruction pointer right
    Q    Push value of variable `q`
    )    Increment top of stack
    7    Push 7
    =    If the top two elements of the stack are equal (`q` and 7)
        v    Send the instruction pointer down
        <    Send the instruction pointer left
        0    Push 0
        q    Pop stack and write to variable `q`
        N    Push value of variable `n`
        (    Decrement top of stack
        n    Pop stack and write to variable `n`
        O    Push value of variable `o` ("0")
        c    Pop stack and write to variable `c` (current character)
        v    Send instruction pointer down
        <    Send instruction pointer left
        Go to [loop-continuation]
    Else
    _    Pop stack (remove the 7)
    q    Pop stack and write to variable `q`
    v    Send instruction pointer down
    v    Same as previous, only for readability
    <    Send instruction pointer left
    <    Same
    Go to [loop-continuation]
[loop-continuation]
Else
v.   Send instruction pointer down
v.   Same
>.   Send instruction pointer right
C.   Push value of variable `c` to stack (current character)
O.   Push value of variable `O` ("0")
=.   If the top two elements of the stack (current character and "0") are equal
    ^    Send instruction pointer up
    >.   Send instruction pointer right
    T.   Push to stack value of variable `t` (current state, J or K)
    J.   Push to stack value of variable `j` ("J")
    =    If the top two elements of the stack (current state and "J" are equal)
        ^.   Send instruction pointer up
        >.   Send instruction pointer left
        K.   Push value of variable `k` ("K")
        t.   Pop stack and write to variable `t`
        v.   Send instruction pointer down
        Continue at the [here] indicator
    Else
    J    Push value of variable `j` ("J")
    t.   Pop stack and write to variable `t`
    v.   Send instruction pointer down
    Continue at the [here] indicator
[here]
>.   Send instruction pointer right
^.   Send instruction pointer up
^.   Same
T.   Push value of variable `t` ("J" or "K")
~.   Print top of stack without newline
Go to [start of loop] indicator

That can be clarified to :

while has not reached end of string:
    increment character_index
    current_character = string[character_index]
    if current_character is a 1:
        increment one_count
        if one_count is 7:
            set one_count to zero
            decrement character_index
            current_character = 0
    if current_character is a 0:
        if state is J:
            state = K
        else:
            state = J
    print state
print newline
exit

run online - largest input

run online - enter input yourself

Answer 9

Red, 79 bytes

func[x][p: 0 x: replace/all x"111111""1111110"forall x[prin p: 49 - x/1 xor p]]

Try it online!

Both input and output are strings of \$1\$s and \$0\$s. Output is done by printing. Despite the unwieldy string replacement, other ways to account for the extra zero bit tend to be even longer.

Answer 10

Retina 0.8.2, 33 32 bytes

1{6}
$&0
{+rT`d`JK`K.
1T`d`KJ`\d

Try it online! Link includes test cases. Explanation:

1{6}
$&0

Perform bit-stuffing.

{`

Make as many replacements as possible.

+rT`d`JK`K.

Change 0 after a K to J and 1 after a K to K. Change starting with the character after the last K (and working back, not that it matters), and keep replacing characters until there are no digits after a K.

1T`d`KJ`\d

The first remaining digit is not after a K, so change 0 to K and 1 to J.

Answer 11

Charcoal, 24 bytes

≔⪫⪪Ｓ×1⁶⁺×1⁶0θ⭆θ§JK№…θ⊕κ0

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

≔⪫⪪Ｓ×1⁶⁺×1⁶0θ

Perform bit-stuffing.

⭆θ§JK№…θ⊕κ0

For each prefix of the string count the number of 0s and output K if it is odd and J if it is even.

Answer 12

K (ngn/k), 21 bytes

0=\.'(t,$0)/(t:6#$1)\

Try it online!

Takes input as a string of "1"s and "0"s. Returns a list of 0s (for J) and 1s (for K).

• do a string replace of "111111" with "1111110"
  • (t:6#$1) store "111111" in variable t
  • (t,$0) append a "0" to the end of t, generating "1111110"
• .' convert each character to an integer
• 0=\ use a equals-scan, seeded with 0 (this does the non-return-to-zero part)

Answer 13

Haskell, 85 bytes

map("JK"!!).(0%)
j%(1:1:1:1:1:1:y)=j:j:j:j:j:j:j%(0:y)
j%(i:y)|k<-i^j*j^i=k:k%y
j%e=e

Try it online!

Answer 14

C (gcc), 84 80 78 bytes

-6 thanks to @ceilingcat

x;c;a(char*p){for(c=0,x=1;*p;c>5&&a(L"10"+x))putchar(x^=*p<49),c=*p++/49*-~c;}

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

For output as actual J and K, Try it online!

Decoder