Convert to UTF-∞

Question

It's 22022 and the Unicode consortium is having a problem. After the writing system of the ⮧⣝Ⅲⴄ⟢⧩⋓⣠ civilization was assigned the last Unicode block, the consortium members have been scrambling to find a new encoding to replace UTF-8. Finally UTF-∞, a proposal by Bob Rike, was adopted. UTF-∞ is backwards compatible with UTF-8. If you know how UTF-8 works, then TLDR; UTF-∞ is the natural extension of UTF-8.

UTF-∞, like UTF-8, encodes an integer to some sequence of bytes like so (each byte shown as 8 bits)

xxxxxxxx 10xxxxxx 10xxxxxx 10xxxxxx ...

If the sequence of bytes has length \$n\$, then the first \$n\$ x:s (from left to right), are set to 1 and the \$n+1\$:th x is set to 0. The rest of the x:s encode a big-endian binary representation of the integer.

There is an exception. If the length of the sequence is 1 (meaning the input number is less than 128), then the encoding looks as follows:

0xxxxxxx

Where the x:s contain the binary representation of the integer.

Also, in order for an encoding to be valid, the minimum amount of bytes has to be used (no overlong encodings).

Your task is to take in a non-negative integer and output the UTF-∞ representation of the integer. You can output a list/string of bytes or a list of numbers between 0 and 255 inclusive. This is code-golf so shortest code wins.

Example

Let's take the input 8364 (the euro symbol "€") as an example. We somehow know that we need 3 bytes, so \$n=3\$. Let's take

xxxxxxxx 10xxxxxx 10xxxxxx 10xxxxxx ...

And take the first 3 bytes:

xxxxxxxx 10xxxxxx 10xxxxxx

Next, the first \$n\$ "x"s are set to 1:

111xxxxx 10xxxxxx 10xxxxxx

And then the leftmost "x" is set to 0. (index \$n+1\$ before any "x"s were replaced)

1110xxxx 10xxxxxx 10xxxxxx

Finally, we fill the binary expansion of 8364 (which is 10 0000 1010 1100) into the remaining "x"s

11100010 10000010 10101100

And convert to bytes:

[226, 130, 172]

Now you might wonder how we know what value of \$n\$ to use? One option is trial and error. Start from \$n=1\$ and increment \$n\$ until we find an \$n\$ where the binary expansion of our input fits.

If we had the input 70368744177663 (\$n=9\$) we would start like so:

xxxxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx

and then

11111111 1010xxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx

and then fill the binary expansion of 70368744177663

Test cases

0 -> [0]
69 -> [69]
127 -> [127]
128 -> [194, 128]
1546 -> [216, 138]
2047 -> [223, 191]
2048 -> [224, 160, 128]
34195 -> [232, 150, 147]
65535 -> [239, 191, 191]
65536 -> [240, 144, 128, 128]
798319 -> [243, 130, 185, 175]
2097151 -> [247, 191, 191, 191]
2097152 -> [248, 136, 128, 128, 128]
30606638 -> [249, 180, 176, 148, 174]
67108863 -> [251, 191, 191, 191, 191]
67108864 -> [252, 132, 128, 128, 128, 128]
20566519621 -> [254, 147, 137, 183, 130, 189, 133]
68719476735 -> [254, 191, 191, 191, 191, 191, 191]
68719476736 -> [255, 129, 128, 128, 128, 128, 128, 128]
1731079735717 -> [255, 153, 140, 140, 153, 136, 166, 165]
2199023255551 -> [255, 159, 191, 191, 191, 191, 191, 191]
2199023255552 -> [255, 160, 160, 128, 128, 128, 128, 128, 128]
64040217759022 -> [255, 174, 163, 186, 134, 155, 164, 180, 174]
70368744177663 -> [255, 175, 191, 191, 191, 191, 191, 191, 191]
70368744177664 -> [255, 176, 144, 128, 128, 128, 128, 128, 128, 128]
34369578119952639221217025744100729453590194597032 -> [255, 191, 191, 191, 191, 165, 184, 145, 129, 139, 182, 177, 159, 176, 167, 155, 139, 159, 138, 163, 170, 143, 151, 141, 156, 154, 134, 183, 176, 175, 170, 178, 168]

Answer 1

Charcoal, 47 bytes

Ｎθ≔÷⁺³Ｌ↨貦⁵ηＩ⎇‹θ¹²⁸θＥ↨⁺θ⁻Ｘ⁶⁴η×⁴Ｘ³²η⁶⁴⁺ι×⁶⁴⁺²¬κ

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

Ｎθ

Input the integer.

≔÷⁺³Ｌ↨貦⁵η

Calculate the number of bytes the extended representation would take.

Ｉ⎇‹θ¹²⁸θ

If the integer is less than 128 then just output the integer again, otherwise...

Ｅ↨⁺θ⁻Ｘ⁶⁴η×⁴Ｘ³²η⁶⁴⁺ι×⁶⁴⁺²¬κ

... calculate n-2 high-level bits, add that to the integer, convert to base 64, then add 192 to the first byte and 128 to the remaining bytes.

Answer 2

JavaScript (Node.js),  104  103 bytes

Saved 1 byte thanks to @emanresuA

Expects a BigInt. Returns a comma-separated string of bytes.

n=>n>127?(g=k=>k>63?g(k>>6n)+[,k&63n|128n]:k|192n)(2n**(x=(h=n=>n?-~h(n/2n):3n)(n)/5n)-4n<<x*5n|n):n+''

Try it online!

92 bytes

An alternate version taking a standard JS number. It only works up to 0x3FFFFFF, which somewhat defeats the purpose of using UTF-∞. :-/

n=>n>>7?(g=k=>k>>6?g(k>>6)+[,k&63|128]:k|192)(2**(x=(h=n=>n?-~h(n>>1):3)(n)/5|0)-4<<x*5|n):n

Try it online!

How?

This is essentially the same method as @Neil's.

Using the recursive function \$h\$, we compute \$x=\left\lfloor(b+3)/5\right\rfloor\$, where \$b\$ is the number of bits in the input.

We compute \$2^x-4\$ (a bit mask consisting of \$x-2\$ ones followed by \$2\$ zeros). We shift it by \$5x\$ positions to the left and OR it with \$n\$.

Using the recursive function \$g\$, we convert the result to base \$64\$ in big-endian order. We add \$192\$ to the leading byte and \$128\$ to the other ones.

Answer 3

JavaScript (Node.js), 171 bytes

n=>n<128?n:(F='0bxxxxxxxx '.repeat(c=((d=n.toString(2)).length+3)/5|0)[r='replace'](/ 0bxx/g,' 0b10',i=0))[r](/x/g,_=>i++<c?1:d.padStart(5*c+3,0)[i-c])[r](/0b\d{8}/g,eval)

Try it online!

Since n<128 is an edgecase, just handle it there and then.

Next, the code determines the number of bytes using a simple formula: if there are c bytes, then there are 5c+1 x's, so we use that. This means subtracting one from the number of bits in the binary representation and dividing that by five. We repeat xxxxxxxx that many times. Replace the first two x's of any byte that is not the first with a 10, then replace the remaining x's with the (padded) binary representation of n, then evaluate each byte.

Output format: as a number for n<128, as a space-separated string (with trailing newline) otherwise. Let me know if this is not allowed.

Fails on last testcase due to JavaScript's limitations.

Thanks @Neil for -7 bytes.

Answer 4

JavaScript (Node.js), 137 bytes

n=>n<128?[n]:eval(`[0b${('1'.repeat((L=(s=n.toString(2)).length+3)/5)+'0'.repeat(~(4.8*~L%6-2))+s).match(/^.{8}|.{6}/g).join`n,0b10`}n]`)

Try it online!

StackExchange code highlight is broken again... Not sure if using string based idea could golf some more bytes or not.

Answer 5

05AB1E, 33 bytes

žy@ibg3+5÷U64Xm32Xm4*-+64вāΘÌ64*+

Port of @Neil's Charcoal answer.

Try it online or verify all test cases.

Explanation:

In pseudo-code:

For inputs \$<128\$, simply output the input
For inputs \$\geq128\$:

1. With \$n\$ as input, first calculate: \$x=\left\lfloor\frac{len(bin(n))+3}{5}\right\rfloor\$
2. Then calculate \$y=64^x-4\times32^x+n\$
3. Convert this \$y\$ to a base-64 list
4. Add 128 to each item, and an additional 64 to the very first item, which is the intended output

žy@i             # If the (implicit) input-integer is >= 128:
    b            #  Convert the (implicit) input to a binary string
     g           #  Pop and push its length
      3+         #  Add 3
        5÷       #  Integer-divide that by 5
          U      #  Pop and store it in variable `X`
    64Xm         #  Push 64 to the power `X`
        32Xm     #  Push 32 to the power `X`
            4*   #  Multiply it by 4
              -  #  Subtract it from each other
               + #  Add the (implicit) input to it
    64в          #  Convert this integer to a base-64 list
       ā         #  Push a list in the range [1,length] (without popping)
        Θ        #  Convert every non-1 to 0 (with an ==1 check)
         Ì       #  Add 2 to each
          64*    #  Multiply each by 64
             +   #  Add the values at the same positions in the lists together
                 #  (after which this list is output implicitly as result)
                 # (implicit else:)
                 #  (implicitly output the implicit input)

Answer 6

JavaScript (Node.js), 101 bytes

n=>(h=x=>x>>8n?[...h(x>>6n),x%64n+128n]:[x])((g=x=>n>>7n?n>>1n+5n*x?g(++x):64n**x-32n**x:x)(0n)*4n+n)

Try it online!