8
\$\begingroup\$

In the UTF-8 encoding bytes of the Form 10****** can only appear within multi-byte sequences, with the length of the sequence already being determined by the first byte. When UTF-8 text is split within a multi-byte UTF-8 character sequence, this prevents that the second part of the sequence is wrongly detected as another character. While in for normal Text files this error-checking is a good idea (and prevents unwanted ASCII control characters/null-bytes from appearing in the byte-stream), for code-golf this redundancy is just wasting bits.

Your task is to write two programs or functions, one decoder and one encoder converting between code-points and "compressed UTF-8", defined the following way:

1 byte sequence:
bytes 0x00 to 0xbf  -> code-points 0x00 -> 0xbf

2 byte sequence  (code-points 0x00 -> 0x1fff):
0b110AAAAA 0bBBCCCCCC
-> code-point 0b (BB^0b10) AAAAA CCCCCC

3 byte sequence (code-points 0x00 -> 0xfffff):
0b1110AAAA 0bBBCCCCCC 0bDDEEEEEE
-> code-point 0b (BB^10) (DD^10) AAAA CCCCCC EEEEEE

4 byte sequence (code-points 0x00 -> 0x7ffffff):
0b11110AAA 0bBBCCCCCC 0bDDEEEEEE 0bFFGGGGGG
-> code-point 0b (BB^10) (DD^10) (FF^10) AAA CCCCCC EEEEEE GGGGGG

Or in short form: The compressed UTF-8 code-point for a sequence of bytes, is the regular UTF-8 code-point for that byte-sequence, with the difference of the high two bits and 0b10 prepended on the start of the number.

Examples:

decode:
[] -> []
[0xf0, 0x80, 0x80, 0x80] -> [0x00]
[0x54, 0x65, 0x73, 0x74] -> [0x54, 0x65, 0x73, 0x74]
[0xbb, 0xb5, 0xba, 0xa9, 0xbf, 0xab] -> [0xbb, 0xb5, 0xba, 0xa9, 0xbf, 0xab]
[0xc2, 0xbb, 0xc2, 0xb5, 0xc2, 0xba, 0xc2, 0xa9, 0xc2, 0xbf, 0xc2, 0xab] -> [0xbb, 0xb5, 0xba, 0xa9, 0xbf, 0xab]
[0xe2, 0x84, 0x95, 0xc3, 0x97, 0xe2, 0x84, 0x95] -> [0x2115, 0xd7, 0x2115]
[0xf0, 0x9f, 0x8d, 0x8f, 0xf0, 0x9f, 0x92, 0xbb] -> [0x1f34f, 0x1f4bb]
[0xef, 0x8d, 0xcf, 0xef, 0x92, 0xfb]             -> [0x1f34f, 0x1f4bb]

encode:
[] -> []
[0x54, 0x65, 0x73, 0x74] -> [0x54, 0x65, 0x73, 0x74]
[0xbb, 0xb5, 0xba, 0xa9, 0xbf, 0xab] -> [0xbb, 0xb5, 0xba, 0xa9, 0xbf, 0xab]
[0x2115, 0xd7, 0x2115] -> [0xe2, 0x84, 0x95, 0xc3, 0x97, 0xe2, 0x84, 0x95]
[0x1f34f, 0x1f4bb] -> [0xef, 0x8d, 0xcf, 0xef, 0x92, 0xfb]
// [0x1f34f, 0x1f4bb]=[0b1_1111_001101_001111,0b1_1111_010010_111011]
// [0xef, 0x8d, 0xcf, 0xef, 0x92, 0xfb]=[0b11101111,0b10001101,0b11001111,0b11101111,0b10010010,0b11111011]

Rules

  • You are allowed to use your languages internal string representation instead of code-point arrays for input/output
  • When encoding a code-point you should return the shortest sequence representing that code-point
  • The input may contain multiple code-points / bytes representing multiple code-points
  • You only need to handle code-points in the range (0x00 to 0x10ffff)
  • You score will be the sum of the lengths of the two programs
  • This is the shortest solution wins
\$\endgroup\$
1
  • \$\begingroup\$ That's not the only convenience that you get from UTF-8, for instance it's compatible with null-terminated strings but your encoding can have embedded nulls e.g. [0x80000] becomes [0xe0, 0x00, 0x80]. \$\endgroup\$
    – Neil
    Aug 15, 2023 at 0:22

3 Answers 3

4
\$\begingroup\$

JavaScript (ES10), 228 bytes

This code is solely based on bitwise operations. There may be a better way with some built-ins. At any rate, I can't say I'm very happy with it.

Decoder (105 bytes)

a=>a.flatMap(i=v=>i--?(n=n<<6|v&63|(v&192^128)<<5*s-4*i,i?[]:n):(s=i=(v>>4)**4>>14)?(n=v&~0>>>26+s,[]):v)

Try it online!

A somewhat interesting formula in there is (v >> 4) ** 4 >> 14 which turns the leading byte \$v\$ into the number of extra bytes in the sequence.

v >> 4 (v >> 4) ** 4 (v >> 4) ** 4 >> 14
0b0000 (0x0) 0b0000000000000000 0
0b0001 (0x1) 0b0000000000000001 0
0b1011 (0xB) 0b0011100100110001 0
0b1100 (0xC) 0b0101000100000000 1
0b1101 (0xD) 0b0110111110010001 1
0b1110 (0xE) 0b1001011000010000 2
0b1111 (0xF) 0b1100010111000001 3

Encoder (123 bytes)

a=>a.flatMap(n=>n<192?n:(s=n>>13?n>>20?8:4:2,g=i=>i<s?[...g(i*2),n/i**6&63|n/s**5/i/i&192^128]:[n/s**6&63/s|384/s|192])(1))

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ From what I understand, g=i=>i<s?... is an arrow function expression with a ternary condition as it's return value and n>>13?n>>20?8:4:2 represents a value obtained from two ternary conditions assigned to s? Took me a minute to wrap my head around this but wow I'm grateful no one writes code like this in the wild! Great work! \$\endgroup\$
    – Malekai
    Aug 14, 2023 at 18:45
  • 3
    \$\begingroup\$ @Malekai That's correct. Here is a formatted version of the source. \$\endgroup\$
    – Arnauld
    Aug 14, 2023 at 18:50
2
\$\begingroup\$

Perl 5, 570 bytes

sub{$_=join'',map sprintf('%08b',$_),@_;%c=qw(00 10 01 11 10 00 11 01);my@r;push@r,oct'0b'.(s/^110(.{5})(..)(.{6})// ? "$c{$2}$1$3":s/^1110(.{4})(..)(.{6})(..)(.{6})// ? "$c{2}$c{$4}$1$3$5":s/^11110(...)(..)(.{6})(..)(.{6})(..)(.{6})// ? "$c{$2}$c{$4}$c{$6}$1$3$5$7":s/.{8}//*$&) while y///c;@r},
sub{map 128^oct"0b$_",map{$_=sprintf"%032b",$c=$_;$c>0xfffff?do{/(..)(..)(..)(...)(.{6})(.{6})(.{6})$/;"01110$4",$1.$5,$2.$6,$3.$7}:$c>0x1fff?do{/(..)(..)(....)(.{6})(.{6})$/;"0110$3",$1.$4,$2.$5}:$c>0xbf?do{/(..)(.{5})(.{6})$/;"010$2",$1.$3}:do{/(.)(.{7})$/;(1-$1).$2}}@_}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 170 bytes

Decoder, 81 bytes:

≔⮌AθWθ«≔⊟θι¿‹ι¹⁹²⊞υι«≔⍘ι²η≔⌕η0ζ≔E⊖ζ⍘⁺⁶⁴⁰⊟θ²ε⊞υ⍘⁺⁺⭆ε✂겦⁴¦¹✂η⊕ζχ¹⭆ε✂κ⁴χ¹¦²»»Eυ⍘ι¹⁶

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

≔⮌Aθ

Reverse the input so that the bytes can be easily processed separately.

Wθ«

Repeat while there is still input to process.

≔⊟θι

Get the next byte.

¿‹ι¹⁹²⊞υι«

If this is a single byte code, then just push the code, otherwise:

≔⍘ι²η

Convert the first byte to binary.

≔⌕η0ζ

Get the total number of bytes in the sequence.

≔E⊖ζ⍘⁺⁶⁴⁰⊟θ²ε

Get the remaining bytes, add 640 to each, and convert them to base 2. This results in a string of the form 1XBBCCCCCC.

⊞υ⍘⁺⁺⭆ε✂겦⁴¦¹✂η⊕ζχ¹⭆ε✂κ⁴χ¹¦²

Extract the B and C portions of those bytes, sandwiching the A bits from the first byte in between, then convert the final string back from base 2.

»»Eυ⍘ι¹⁶

Output everything in hex for convenience (decimal would save 4 bytes).

Encoder, 89 bytes:

FA¿‹ι¹⁹²⊞υι«≔÷L↨鲦⁷θ≔⟦⟧ηFθ«⊞η﹪ι⁶⁴≧÷⁶⁴ι»≔X²⁻⁶θθ⊞υ⁺﹪ιθ⁻²⁵⁶⊗θF⮌Eη⁺κ×⁶⁴﹪⁺²÷ι×θX⁴λ⁴⊞υκ»Eυ⍘ι¹⁶

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

FA

Loop over the input code points.

¿‹ι¹⁹²⊞υι«

If this is a single byte code point then just push the byte, otherwise:

≔÷L↨鲦⁷θ

Get the number of additional bytes.

≔⟦⟧ηFθ«⊞η﹪ι⁶⁴≧÷⁶⁴ι»

Extract the bottom six bits of those bytes.

≔X²⁻⁶θθ⊞υ⁺﹪ιθ⁻²⁵⁶⊗θ

Push the first byte.

F⮌Eη⁺κ×⁶⁴﹪⁺²÷ι×θX⁴λ⁴⊞υκ

For each additional byte, extract its top two bits and push it.

»Eυ⍘ι¹⁶

Output everything in hex for convenience (decimal would save 4 bytes).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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