5 ms·

Reading bits in far too many ways

117 points by makmanalp 9y ago

jrochkind1 9y ago
This article is awesome, I don't work in this kind of thing at all, and I feel like it's a good exersize for my brain.
cpach 9y ago
Fun small educational project: If you want to learn how to work with units smaller than a byte, implement Base64 from scratch. It’s really fun!
- psykotic 9y ago
  In case anyone might be mislead given the topic of this article, you shouldn't do base64 encoding with a general purpose routine like getbits(). Since 3 * 8 / 6 = 4 you can process the input bytes in groups of 3 to avoid straddling issues (ideally with an unaligned 32-bit load if they're fast on your platform). Then your inner loop will look like this: uint32_t triple = *(uint32_t *)in; *out++ = base64[triple & MASK]; *out++ = base64[(triple >> 6) & MASK]; *out++ = base64[(triple >> 12) & MASK]; *out++ = base64[(triple >> 18) & MASK]; in += 3; (The 32-bit load can read one byte past the end of the buffer, so allocate extra space or stop the loop early.)
- wmu 9y ago
  Better would be the Huffman coding; one has to deal with variable bitfield widths.
  - zmodem 9y ago
    In fact, that appears to be where the author is coming from. Part 2 mentions techniques coming from the Kraken Huffman decoder (http://www.radgametools.com/oodlecompressors.htm http://www.radgametools.com/oodlecompressors.htm)
userbinator 9y ago
The first major decision to make is whether fields are packed MSB-first or LSB-first Unfortunately in many cases like image and video codecs, that decision has been made for you already --- and not in the direction that's most efficient for a CPU (but of course is pretty much immaterial for hardware.) I suspect "It’s easy to fool yourself into thinking that one variant is better than another because it looks prettier" was what drove those decisions. The big-endian/MSB-first order requires extra "bit movement" if you are maintaining a bit buffer in a register, since the bits of interest are always going to reside in the topmost bits, but you often need them in the lowest bits to use them. With little-endian/LSB-first, the bits of interest are already in the lowest position, and naturally "fall off the end" as you shift right and replenish into the upper bits. IMHO another reason to prefer little-endian: it's very logically consistent.
- jandrese 9y ago
  Personally I don't care so much which is better, I just wish people would choose one and stick with it. I mean eventually 2's complement math managed to win, why can't LSB? Of course the goddamn Internet decided to go MSB, so we'll forever be stuck with that friction. And don't get me started on line endings. Gah!
- deleted 9y ago
  [deleted]
- ghusbands 9y ago
  Your reasoning about which end has interesting bits has no basis in how CPUs actually do any of their work The byte-ordering does not fundamentally affect how operations are implemented. Us humans often find little-endian confusing because we write numbers big-endian. If you have the number 258 (0x102) in memory in little endian (which most computers use) 32-bit, it is hex 02 01 00 00, binary 00000010 00000001 00000000 00000000. If you bit-shift that one to the right without care, you end up with 00000001 00000000 10000000 00000000, hex 01 00 80 00, which is 8,388,609. To fix it, write your digits also in little-endian order, so the first number is 10000000 010000000 00000000 00000000. Then the shift operations match expectations.
zmodem 9y ago
Part 2: https://news.ycombinator.com/item?id=16419774 https://news.ycombinator.com/item?id=16419774
ahartmetz 9y ago
Almost everything on this guy's blog is amazing if you are interested in hardware, optimization and that kind of thing.

117 points by makmanalp 9y ago

This article is awesome, I don't work in this kind of thing at all, and I feel like it's a good exersize for my brain.

Fun small educational project: If you want to learn how to work with units smaller than a byte, implement Base64 from scratch. It’s really fun!

psykotic 9y ago
In case anyone might be mislead given the topic of this article, you shouldn't do base64 encoding with a general purpose routine like getbits(). Since 3 * 8 / 6 = 4 you can process the input bytes in groups of 3 to avoid straddling issues (ideally with an unaligned 32-bit load if they're fast on your platform). Then your inner loop will look like this: uint32_t triple = *(uint32_t *)in; *out++ = base64[triple & MASK]; *out++ = base64[(triple >> 6) & MASK]; *out++ = base64[(triple >> 12) & MASK]; *out++ = base64[(triple >> 18) & MASK]; in += 3; (The 32-bit load can read one byte past the end of the buffer, so allocate extra space or stop the loop early.)
wmu 9y ago
Better would be the Huffman coding; one has to deal with variable bitfield widths.
- zmodem 9y ago
  In fact, that appears to be where the author is coming from. Part 2 mentions techniques coming from the Kraken Huffman decoder (http://www.radgametools.com/oodlecompressors.htm http://www.radgametools.com/oodlecompressors.htm)

userbinator 9y ago

The first major decision to make is whether fields are packed MSB-first or LSB-first Unfortunately in many cases like image and video codecs, that decision has been made for you already --- and not in the direction that's most efficient for a CPU (but of course is pretty much immaterial for hardware.) I suspect "It’s easy to fool yourself into thinking that one variant is better than another because it looks prettier" was what drove those decisions. The big-endian/MSB-first order requires extra "bit movement" if you are maintaining a bit buffer in a register, since the bits of interest are always going to reside in the topmost bits, but you often need them in the lowest bits to use them. With little-endian/LSB-first, the bits of interest are already in the lowest position, and naturally "fall off the end" as you shift right and replenish into the upper bits. IMHO another reason to prefer little-endian: it's very logically consistent.

jandrese 9y ago
Personally I don't care so much which is better, I just wish people would choose one and stick with it. I mean eventually 2's complement math managed to win, why can't LSB? Of course the goddamn Internet decided to go MSB, so we'll forever be stuck with that friction. And don't get me started on line endings. Gah!
deleted 9y ago
[deleted]
ghusbands 9y ago
Your reasoning about which end has interesting bits has no basis in how CPUs actually do any of their work The byte-ordering does not fundamentally affect how operations are implemented. Us humans often find little-endian confusing because we write numbers big-endian. If you have the number 258 (0x102) in memory in little endian (which most computers use) 32-bit, it is hex 02 01 00 00, binary 00000010 00000001 00000000 00000000. If you bit-shift that one to the right without care, you end up with 00000001 00000000 10000000 00000000, hex 01 00 80 00, which is 8,388,609. To fix it, write your digits also in little-endian order, so the first number is 10000000 010000000 00000000 00000000. Then the shift operations match expectations.

zmodem 9y ago

Part 2: https://news.ycombinator.com/item?id=16419774 https://news.ycombinator.com/item?id=16419774

ahartmetz 9y ago

Almost everything on this guy's blog is amazing if you are interested in hardware, optimization and that kind of thing.