Encoder/Decoder for efficient number storage!

Question

Description

Inspired by this question, write a program/function to encode a number and a program (possibly the same as the first) to decode a bitstream in variable-length encoding as follows (taken from that question's answer, slightly modified):

Represent the string x using the following encoding:

$$0, x_k, \dots, 0, x_2, 0, x_1, 1, x_0$$

where \$x_0\$ is just \$x\$, then \$x_{i+1} = \mathrm{len}(x_i)\$ is a binary representation of the length of \$x_i\$ in bits (namely, \$\mathrm{len}(x_i)=\mathrm{ceil}(\log_2 x_i)\$, for \$i \ge 1\$), and \$k\$ is the smallest \$k \ge 1\$ such that \$x_k \le 3\$.
In particular, you always encode \$x_k\$ with 2 bits, and encode \$x_i\$ with \$x_{i+1}\$ bits.

Some example encodings:

Decimal	Encoded
0	00110
1	00111
2	010110
3	010111
4	0111100
8	011010011000
127	011011111111111

Note that based on this encoding, the first bit is always 0, and the next 2 bits afterwards always encode the length of the next part.

Input/Output

For the encoder, it will take as input a list of non-negative integers, which may be empty (in any list representation you like), and output the string as per the encoding above. When encoding multiple numbers, simply concatenate the encoding. If the input is an empty list, output empty string.

For the decoder, it will take as input a (possibly invalid encoding, but always consists only of 0 and 1) bit string, and output a list of integers it encodes (in the same representation as the input to your encoder). If the string is an invalid encoding, you can output anything that cannot be misconstrued as a valid list of integers. For example, you can just output "INVALID" as the whole output, or you output "X" after outputting partially decoded list of integers (e.g., when the first part of the string is valid, but the later one isn't). As long as your invalid output cannot be read as a list of integers as a whole (in the same representation you use for the encoder input), it's fine. This includes terminating with an exception or a non-zero exit code (since it's also not a valid input to the encoder).

Scoring

This is code golf, the score of an answer is the sum of the number of bytes in both programs. If your program can do both in the same program, the length of that program is the score. Lowest score wins. Standard code golf rules apply.

Test Cases

Some test cases (input, then output on the next line, separated by a blank line):

Encoder

2
010110

1 5 3
001110111101010111

0 0 1
001100011000111

8 127 512 987654321
0110100110000110111111111110110100010101100000000001101010111101111010110111100110100010110001

The last test case is an empty list as input, and empty string as output

Decoder

010110
2

001110111101010111
1 5 3

001100011000111
0 0 1

00111011110010111
Invalid (a new number starts with 1)

1
Invalid (a new number starts with 1)

0011000110001
Invalid (not complete)

001100011001101001100
Invalid (not complete)

0011000110011010
Invalid (not complete)

0110100110000110111111111110110100010101100000000001101010111101111010110111100110100010110001
8 127 512 987654321

The last test case is an empty string, outputting empty list (which is empty string in this case, but it depends on your list representation)

Answer 1

JavaScript (ES6), 170 bytes

Encoder, 85 bytes

a=>a.map(g=(n,_,i,b=n.toString(2))=>(i=+!!i)|n>3?g(b.length)+i+b:i+=n<2?0+b:b).join``

Try it online!

Commented

a =>                // a[] = input array
a.map(g = (         // g is a recursive callback function taking:
  n,                //   n = current integer
  _,                //   the index is ignored
  i,                //   the reference to the array is used as a flag
                    //   (either defined or undefined)
  b = n.toString(2) //   b = binary representation of n
) =>                //
  (i = +!!i) |      //   turn i into either 0 or 1
  n > 3 ?           //   if i = 1 or n is greater than 3:
    g(b.length) +   //     do a recursive call with the length of b
    i + b           //     append i, followed by b
  :                 //   else:
    i +=            //     append i, followed by:
      n < 2 ?       //       if n is less than 2:
        0 + b       //         a leading '0' and b
      :             //       else:
        b           //         just b
).join``            // end of map(); join everything

Decoder, 85 bytes

Throws an error if the input is invalid.

f=(s,n=3,S=s.slice(n))=>s?(k='0b'+s.slice(1,n))[n]?s>k?[+k,...f(S)]:f(S,-~k):_:n-3||s

Try it online!

Commented

f = (             // f is a recursive function taking:
  s,              //   s = input string
  n = 3,          //   n = length of current bit block
  S = s.slice(n)  //   S = remaining string after the current block
) =>              //
s ?               // if s is not empty:
  ( k =           //   define k as:
    '0b' +        //     the binary prefix followed by
    s.slice(1, n) //     the current bit block without the leading digit
  )[n] ?          //   if k is as long as expected:
    s > k ?       //     if the leading digit is '1':
      [ +k,       //       append k, coerced to an integer
       ...f(S) ]  //       followed by the result of a recursive call with S
    :             //     else:
      f(S, -~k)   //       do a recursive call with S and n = k + 1
  :               //   else:
    _             //     force an error (undefined variable)
:                 // else:
  n - 3 ||        //   force an error if n is not equal to 3
  []              //   otherwise, stop the recursion properly

Answer 2

Python3, 300 bytes

Encoder, 142 bytes

def e(x,l='1'):return''.join(e(s)for s in x)if type(x)is list else '0'+f"{x>>1}{x&1}"if x<4 and l=='0'else e(len(bin(x)[2:]),'0')+l+bin(x)[2:]

Try it online!

Decoder 158 bytes

def d(s,l=2,t=0):return''if s==''and t==0else d(s[1+l:],int(s[1:1+l],2),1)if s[0]=='0'else str(int(s[1:1+l],2))+' '+d(s[1+l:],2,0)if s[0]=='1'and t==1else 1/0

Try it online!

Answer 3

Charcoal, 115 bytes

Encoder, 43 bytes

ＦＥＡ⟦ι⟧«Ｗ∨⁼¹Ｌι‹³⌊ι⊞ιＬ⍘⌊ι²⪫⮌Ｅι⁺¬λ⁺…0∧λ‹κ²⍘κ²ω

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

ＦＥＡ⟦ι⟧«

Loop over the input list, but wrap each number in its own list.

Ｗ∨⁼¹Ｌι‹³⌊ι

Repeat until the list has at least two elements and the smallest element is no more than 3.

⊞ιＬ⍘⌊ι²

Push the length in binary of the smallest element to the list.

⪫⮌Ｅι⁺¬λ⁺…0∧λ‹κ²⍘κ²ω

Output the elements in binary in ascending order prefixing the last one with 1 and the rest with 0 or 00 if it is less than 2.

Decoder, 72 bytes

Ｗ∧θ⁼§θ⁰0«≔²ηＷ∧∧‹ηＬθ⁼§θ⁰0θ«≔Φκ›μηθ≔⍘…κ⊕η²η»¿‹ηＬθ«⟦Ｉ⍘…Φθλη²⟧≔Φθ›ληθ»≔1θ»Ｌθ

Try it online! Link is to verbose version of code. Will output at least one - at some point if the string is invalid. Explanation:

Ｗ∧θ⁼§θ⁰0«

Repeat until the string has been processed.

≔²η

The first block is of length 2.

Ｗ∧∧‹ηＬθ⁼§θ⁰0θ«

Repeat while there's a valid bit block starting with 0...

≔Φκ›μηθ

... cut the string after the block, and...

≔⍘…κ⊕η²η

convert the block from binary to give the length of the next block.

»¿‹ηＬθ«

If there's still a valid bit block, then...

⟦Ｉ⍘…Φθλη²⟧

... output its value on its own line, and...

≔Φθ›ληθ

... cut the string after the block.

»≔1θ

Otherwise set the string to an invalid value.

»Ｌθ

Output at least one - if the string was invalid.

Answer 4

Python 3, 117+154 = 271 bytes

Represents a list as space-separated integers.

Each is a full program, taking input from stdin, outputting to stdout.

Encoder, 117 bytes

f=lambda n,s=1:f'{f(len(f"{n:b}"),0)if n>3or s else""}{s}{n:0{2-s}b}'
print(''.join(map(f,map(int,input().split()))))

Try it online!

Prints each encoding backward, from the number itself, then consecutively prints the length of the previous number in binary, separated by the right separator. The parameter s represent the separator to be output. Recurse when length is still more than 3, or it is the original number (s=1).

Decoder, 154 bytes

s=input()
r=[]
def f(i,l,z):
 if len(s)==i:return 1/z
 p=int(s[i]);m=int(s[i+1:i+1+l],2)//(1-z*p);p and r.append(m);f(i+1+l,[m,2][p],p)
f(0,2,1)
print(*r)

Try it online!

Interpret the length of the next binary number repetitively, until separator 1 is found, which indicates the final number. Handles invalid encoding by raising ZeroDivisionError (if first bit in a number is not 0, or bitstream ended while original number is not yet found) or ValueError (trying to interpret empty string as number).

The tricky part is handling the invalid encoding.