Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Base-122 – A space efficient alternative to base-64

blog.kevinalbs.com

Post reply on HN
Print view View original

51–60 of 71 posts

Re: Base-122 – A space efficient alternative to base-64

#51

Post by dmbarbour »

zackmorris wrote: post #38

http://blog.kevinalbs.com/base122#a_minor_note_on_the_last_c... Almost a perfect standard, but the prepended one byte header is a mistake IMHO. It makes it impossible to encode when the input size is unknown. Better to encode whether the last chunk is one byte or two at the end of the stream. Please whoever is involved with this, revise the standard to not have a header and call this existing spec a beta. Otherwise,…

It would be easy to do. That 3-bit word just needs to start at 1 (since it encodes fewer than 8 options). Then the fixed 1-bit can instead encode whether another 7-bit segment follows.

Re: Base-122 – A space efficient alternative to base-64

#52

Post by majewsky »

web007 wrote: post #40

Are single-quotes allowed in the spec? There is an explicit call out for "double quote == bad", but single quotes are also valid property delimeters in HTML.

If your property string is enclosed in a double quote, then a single quote in the payload is fine. (Otherwise, a lot of inline JS in onclick etc. attributes would break. JS allows both types of quotes on string literals for exactly this reason.)

Still, single quotes are somewhat asking for trouble.

Re: Base-122 – A space efficient alternative to base-64

#53

Post by feadog »

ChuckMcM wrote: post #50
userbinator wrote: post #8

The use of codepoints below 32 (space, start of what's usually considered "printable") makes me a bit hesitant. A lot of systems won't preserve those characters. Base85 is a more efficient alternative to base64, and doesn't use that lower range: https://en.wikipedia.org/wiki/Ascii85

I was going to bring up base 85 as well, its a better choice for a variety of reasons. A long time ago I wrote a base encoder class in Java[1] mostly so that we could write a netnews reader in Java but also because I felt UUEncoding was not robust. The challenges of using unprintable characters is a lot more of a headache than anyone pays attention to initially. Lots (and I mean quite a few here) of systems consider…

I wrote a base 92 encoder for the Javascript game I'm working on:

http://www.emergencevector.com/

It's pretty easy to write the decode for the 0-91 integer in Javascript.

    if (ch == "!") {
        return 57;
    } else {
        return ch.charCodeAt(0) - 35;
    }
It doesn't give you that much usable compactness over base 64, though you can easily encode a 360 degree angle with two bits of precision lost. Also, 5 base 92 characters can fully encode 32 bits of binary data. (Of course, since base 85 can do it in 5 characters.)

I'm probably going to go to typed arrays of 32 bit values. Currently, I can encode an entire ship's data in 18 bytes, of which 4 characters is a hash id.

Re: Base-122 – A space efficient alternative to base-64

#54

Post by feadog »

jws wrote: post #32
userbinator wrote: post #8

The use of codepoints below 32 (space, start of what's usually considered "printable") makes me a bit hesitant. A lot of systems won't preserve those characters. Base85 is a more efficient alternative to base64, and doesn't use that lower range: https://en.wikipedia.org/wiki/Ascii85

base 85 also has the interesting property that 4 original bytes fit in 5 encoded bytes. Depending on your processor's memory model and the cost of multiplies compared to shifts this can make it the best performer. This was true on Vax 8200 hardware back in the day. In the same software, with Huffman decoding of JPEGs it was also fastest to create a finite state machine with an 8 bit symbol size. I suspect that is no…

base 85 also has the interesting property that 4 original bytes fit in 5 encoded bytes.

Still useful for Javascript, as the bit shift operators work on 32 bit "registers".

Re: Base-122 – A space efficient alternative to base-64

#55

Post by kevinAlbs »

zackmorris wrote: post #38

http://blog.kevinalbs.com/base122#a_minor_note_on_the_last_c... Almost a perfect standard, but the prepended one byte header is a mistake IMHO. It makes it impossible to encode when the input size is unknown. Better to encode whether the last chunk is one byte or two at the end of the stream. Please whoever is involved with this, revise the standard to not have a header and call this existing spec a beta. Otherwise,…

Good point, I will change that.

Re: Base-122 – A space efficient alternative to base-64

#56

Post by logicallee »

qwename wrote: post #43
logicallee wrote: post #39

meanwhile the Unicode consortium has been hard at work since 1991 to make it possible to encode up to 2.8 MB -- more than enough for most images, short videos, or many PDF files -- in a single character.

Are you referring to UTF-8? If so, this is misleading as you can encode up to 2^21 + 2^16 + 2^11 + 2^7 = 2,164,864 code points, which is not the same as encoding bytes in a single character.

I was making a joke about how ridiculously large Unicode is. Obviously it is not 2 million+ bytes per character! (But the fact that you didn't consider my joke obvious speaks volumes).

Re: Base-122 – A space efficient alternative to base-64

#57

Post by kevinAlbs »

web007 wrote: post #40

Are single-quotes allowed in the spec? There is an explicit call out for "double quote == bad", but single quotes are also valid property delimeters in HTML.

Base-122 encoded strings may contain single quotes but not double quotes. The choice between the two was arbitrary.

Re: Base-122 – A space efficient alternative to base-64

#58

Post by pixl97 »

paulddraper wrote: post #44
xg15 wrote: post #42

Earlier quoted context omitted.

Unless compression cannot be used: https://news.ycombinator.com/item?id=13049898 Also, there are still cases where compression cannot be applied, e.g. if a script naively queries innerHTML. (This wouldn't affect loading time but it could inflate the page's RAM unnecessarily)

Sure, but I'd consider those edge cases to be situations where the treatment is worse than the disease

HTTPS is an edge condition? Over 50 percent of the web is now transferred via HTTPS.

Re: Base-122 – A space efficient alternative to base-64

#59

Post by CiPHPerCoder »

kobeya wrote: post #28
CiPHPerCoder wrote: post #4

My problem with base-122 is simply that it's not an even power of 2. It's very easy to write a cache-timing-safe version of base{16,32,64} encoding for use in encoding/decoding cryptographic keys in configuration files. To wit: https://github.com/paragonie/constant_time_encoding Base-122? Not sure if it's even possible.

I'm pretty sure that Bitcoin has dealt with this issue for its base58 encoding. It might be worth checking if their algorithm is generalizable to other radix sizes.

No, it hasn't. I sent a pull request that attempts to solve this problem for a C# implementation of Base58Check, but there's no way for me to reliably guarantee that data isn't leaking from the divison.

https://github.com/adamcaudill/Base58Check/pull/3

Re: Base-122 – A space efficient alternative to base-64

#60

Post by CiPHPerCoder »

deckar01 wrote: post #35
kobeya wrote: post #28

Earlier quoted context omitted.

I'm pretty sure that Bitcoin has dealt with this issue for its base58 encoding. It might be worth checking if their algorithm is generalizable to other radix sizes.

Check out digit-array if you are interested in the generalized algorithm. The source code is commented with formal math notation for the operations. https://github.com/deckar01/digit-array/blob/master/README.m...

This doesn't appear to address the problem. At all.

https://paragonie.com/blog/2016/06/constant-time-encoding-bo...

Post reply on HN