35
\$\begingroup\$

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 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]
\$\endgroup\$
5
  • 14
    \$\begingroup\$ Trivia: FLAC uses UTF-∞ to encode the absolute position of each audio frame. See xiph.org/flac/format.html#frame_header , "UTF-8 coded sample number / UTF-8 coded frame number". \$\endgroup\$
    – Nayuki
    Feb 27 at 19:22
  • 6
    \$\begingroup\$ It's a nice coincidence that 8 turned sideways is ∞. Kind of like how C++ is sometimes called CXX. \$\endgroup\$
    – Nayuki
    Feb 27 at 19:25
  • 16
    \$\begingroup\$ Just a note: The 8 in UTF-8 is the number of bits in each byte (i.e. each unit), so your "UTF-∞" is a bit misnomed, as it has still 8 bits in each byte, not an infinite number. \$\endgroup\$ Feb 27 at 23:33
  • 2
    \$\begingroup\$ @PaŭloEbermann Good thing the coincidence Nayuki mentioned exists \$\endgroup\$ Feb 28 at 22:14
  • \$\begingroup\$ I wanted to try out making up an algorithm doing that so I made an 8086 DOS program for this. I don't think it would be good for an answer though because it is mostly done for readability and education, not size optimised. It assembles to 524 bytes of machine code; 5696 bytes of source in 360 lines. Here it is: hg.pushbx.org/ecm/cgccutf/file/d78dabb39331/cgccutf.asm \$\endgroup\$
    – ecm
    Mar 1 at 0:13

5 Answers 5

5
\$\begingroup\$

Charcoal, 47 bytes

Nθ≔÷⁺³L↨貦⁵ηI⎇‹θ¹²⁸θE↨⁺θ⁻X⁶⁴η×⁴X³²η⁶⁴⁺ι×⁶⁴⁺²¬κ

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

Nθ

Input the integer.

≔÷⁺³L↨貦⁵η

Calculate the number of bytes the extended representation would take.

I⎇‹θ¹²⁸θ

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

E↨⁺θ⁻X⁶⁴η×⁴X³²η⁶⁴⁺ι×⁶⁴⁺²¬κ

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

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ You can save a byte in the first version by comparing with 63: Try It Online! \$\endgroup\$
    – emanresu A
    Feb 28 at 3:05
  • \$\begingroup\$ @emanresuA I forgot that BigInts can be compared with Numbers. Thanks! \$\endgroup\$
    – Arnauld
    Feb 28 at 10:13
3
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ I think the ||0 is redundant, and there's probably a way of golfing the eval and the Math.ceil. FYI it costs 1 byte to switch to BigInt to be able to process the last test case. \$\endgroup\$
    – Neil
    Feb 27 at 11:42
  • \$\begingroup\$ @Neil, yep, got rid of ||0 just before your comment, but thanks anyway! I'll try the BigInt thing \$\endgroup\$
    – ophact
    Feb 27 at 11:43
  • \$\begingroup\$ @Neil I golfed eval. Could you point me in the right direction as to how to golf Math.ceil? Not sure about that one. \$\endgroup\$
    – ophact
    Feb 27 at 11:48
  • \$\begingroup\$ Nice, I think that's even shorter than what I was thinking of for eval. Math.ceil((d.length-1)/5) equals Math.floor((d.length+3)/5) but this is always a small positive integer so you can use |0 instead of Math.floor. \$\endgroup\$
    – Neil
    Feb 27 at 13:43
2
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ n<128 -> n>>7 \$\endgroup\$
    – emanresu A
    Mar 4 at 8:41
  • \$\begingroup\$ @emanresuA Do you mean n>>7n? \$\endgroup\$
    – tsh
    Mar 4 at 9:27
  • \$\begingroup\$ Oops, never mind. I thought this used regular integers for some reason. \$\endgroup\$
    – emanresu A
    Mar 4 at 9:34
1
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.