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

Base58

en.wikipedia.org

Post reply on HN
Print view View original

21–30 of 44 posts

Re: Base58

#21

Post by ur-whale »

eesmith wrote: post #20
ur-whale wrote: post #17

Base58 isn't a great choice from an implementation point of view. It basically requires a bignum library (or a specialized version that can do divisions of arbitrary long numbers by 58), and conversion is slow as hell. Either you end up pulling in a full bignum library, or you have to use error-prone, clunky specialized code you don't have time to try and understand and verify. Of all the design choices Satoshi made,…

The implementations at https://github.com/search?q=Base58 don't look like they use a bignum package, nor do that look particularly slow or complicated. The main encoding loop for https://github.com/luke-jr/libbase58/blob/master/base58.c is: for (i = zcount, high = size - 1; i high) || carry; --j) { carry += 256 * buf[j]; buf[j] = carry % 58; carry /= 58; } }

There's a divmod by 58 in there. That's dog slow compared to the shifts a power of two basis would require - even when the compiler gets smart about it because it's a constant.

Re: Base58

#23

Post by stcredzero »

dtf wrote: post #9

Not to be confused with Base85. https://en.wikipedia.org/wiki/Ascii85 (used with various alphabets for denser binary encoding in PDF, git binary patches, and the scene files of the Arnold renderer).

In my personal project, I'm using my own Base92 encoding. I wonder why Base85 stops at 85? In particular, you can implement Base92 with one table lookup and one conditional exception. (Which could also be implemented as a table lookup to save branch prediction misses.)

Re: Base58

#24

Post by ChrisLomont »

ur-whale wrote: post #21
eesmith wrote: post #20

Earlier quoted context omitted.

The implementations at https://github.com/search?q=Base58 don't look like they use a bignum package, nor do that look particularly slow or complicated. The main encoding loop for https://github.com/luke-jr/libbase58/blob/master/base58.c is: for (i = zcount, high = size - 1; i high) || carry; --j) { carry += 256 * buf[j]; buf[j] = carry % 58; carry /= 58; } }

There's a divmod by 58 in there. That's dog slow compared to the shifts a power of two basis would require - even when the compiler gets smart about it because it's a constant.

That divmod can be replaced with table walking like CRC code does for division and remainder of fixed values, which is certainly fast, and does not require bignums. Unless you now want to claim all CRC code is also slow as hell or requires bignums. These are solved problems.

Many compilers even expand the code inline to generate fix size divides into mult and shift.

Here's a 4 year old Hacker news thread on compiler tricks then [1]. They're even better now.

[1] https://news.ycombinator.com/item?id=8368639

Re: Base58

#25

Post by adambrenecki »

Another neat encoding is the base-20 character set that Open Location Codes ("plus codes") use:

> The characters that are used in Open Location Codes were chosen by computing all possible 20 character combinations from 0-9A-Z and scoring them on how well they spell 10,000 words from over 30 languages. This was to avoid, as far as possible, Open Location Codes being generated that included recognisable words. The selected 20 character set is made up of "23456789CFGHJMPQRVWX".

https://github.com/google/open-location-code/blob/master/doc...

Re: Base58

#26

Post by eesmith »

ur-whale wrote: post #21
eesmith wrote: post #20

Earlier quoted context omitted.

The implementations at https://github.com/search?q=Base58 don't look like they use a bignum package, nor do that look particularly slow or complicated. The main encoding loop for https://github.com/luke-jr/libbase58/blob/master/base58.c is: for (i = zcount, high = size - 1; i high) || carry; --j) { carry += 256 * buf[j]; buf[j] = carry % 58; carry /= 58; } }

There's a divmod by 58 in there. That's dog slow compared to the shifts a power of two basis would require - even when the compiler gets smart about it because it's a constant.

Thank you for correcting my misunderstanding.

The Ascii85 implementation in Python is 1/70th the performance of the base64 version, and the command-line driver to the base58 implementation I linked to is incredibly slower than the system base64. Profiling shows that the time is indeed spent on the two div/mod lines.

I assume that these are not the fastest possible implementations, but it does show that high performance is not trivial.

Re: Base58

#27

Post by jimktrains2 »

athenot wrote: post #11
decentralised wrote: post #4

Why base-58 instead of standard base-64 encoding? - Don't want 0OIl characters that look the same in some fonts and could be used to create visually identical looking data. - A string with non-alphanumeric characters is not as easily accepted as input. - E-mail usually won't line-break if there's no punctuation to break at. - Double-clicking selects the whole string as one word if it's all alphanumeric. https://githu…

This is a similar encoding as airline reservation numbers, except it also has lowercase characters. But the requirements are very similar. It's amazing how much confusion is removed by suppressing ambiguities between number 0 vs. letter O and number 1 vs. letter I. For reservation numbers, doing away with case makes it easier to speak the number over the phone.

Crockford base32?

Re: Base58

#28

Post by a1369209993 »

ChrisLomont wrote: post #24
ur-whale wrote: post #21

Earlier quoted context omitted.

There's a divmod by 58 in there. That's dog slow compared to the shifts a power of two basis would require - even when the compiler gets smart about it because it's a constant.

That divmod can be replaced with table walking like CRC code does for division and remainder of fixed values, which is certainly fast, and does not require bignums. Unless you now want to claim all CRC code is also slow as hell or requires bignums. These are solved problems. Many compilers even expand the code inline to generate fix size divides into mult and shift. Here's a 4 year old Hacker news thread on compiler…

> Many compilers even expand the code inline to generate fix size divides into mult and shift.

Specificly, u8 divmod 58 can be reduced to a u8->u16 multiply, a right shift, and three conditional subtractions; that's not great, but on a modern CPU it's a afterthought compared to the quadratic loop over the input size.

Re: Base58

#29

Post by lifthrasiir »

eesmith wrote: post #15
lifthrasiir wrote: post #7

Earlier quoted context omitted.

I think the article is good as is, because base58 is actually pretty dissimilar to most binary-to-text encodings. Surprisingly many encodings are just base 2^k (16, 32, 64 and 128 [1]), some have converged to base 85 (because 85^5 / 2^32 ~= 1.03, i.e. just enough to represent 4 octets in 5 units). This is because binary-to-text encodings are not expected to use costly bigint operations for an arbitrary-length payload…

"Base36 and base58 are the only common exceptions" Isn't Ascii85/Base85 at least as common as those? Quoting the Wikipedia entry for it, "Its main modern uses are in Adobe's PostScript and Portable Document Format file formats, as well as in the patch encoding for binary files used by Git" Python includes it as part of the standard library. Using the example from the WP entry: >>> s = r""" Cj@.4Gp$d7F!,L7@ @3BB/F*&OC…

I have explicitly mentioned this:

> [...] some have converged to base 85 (because 85^5 / 2^32 ~= 1.03, i.e. just enough to represent 4 octets in 5 units).

Base 85 does not use bigint, it is just a clever approximation of optimal encoding with 85 symbols.

Post reply on HN