Maybe someone can explain why an encoder would ever create the padding bytes allowed in LEB128. I contributed the parser for LEB128 in apple/swift-binary-parsing and I’m still none the wiser. I’m genuinely mystified.
[deleted]
Bijou64: A variable-length integer encoding
51–60 of 93 posts
Re: Bijou64: A variable-length integer encoding
#52Clever, but one thought crossed my mind; An adveserial package can claim to have a 255 tagged integer but not actually have any followup, tricking the payload parser into an incorrect offset and reading straight off into followup memory. It's a classic thing to check for when dealing with variable length strings or binary, but it may not cross the mind when it's hiding in the Bijou64_decode(*buff, *cr) function.
You have the same issue with LEB128 though, right?
LEB128 can only trick you by at most one byte, (depending on the followup data). Bijou64 can consistently trick you by 8 bytes.
In a contrived example of a pbuf {length:int, payload:byte[1]}
LEB128 can trick you into reading the payload as part of the length, but then hopefully trigger a code check against invalid buffer read. (or one byte outside the struct if the payload is also malicious)
Binou64 can trick you to read 7 bytes into other memory, before any buffer size validation is done.
It's then not uncommon to log with a helpful; "buffer with length: 26624894573377(7 bytes of stolen data) is invalid", or just crash.
It's to the point that Bijou64_decode should perhaps take "end_adress" or "max_read" to catch this kind of attack.
(If you dont validate a malicious pbuf, you're in for a bad time regardless of integer format, but these int formats add their own way to trigger a buffer overrun despite a proper check.)
Re: Bijou64: A variable-length integer encoding
#53This is pretty close to SQLite's varints [0]
[0]: https://www.sqlite.org/src4/doc/1433690d7b/www/varint.wiki
Re: Bijou64: A variable-length integer encoding
#54Earlier quoted context omitted.
This doesn't seem particularly hard to SIMD, especially when the CPU architecture has "compress/expand" horizontal instructions. The first byte fully encodes the length, which is not harder than the continuation bits of (U)LEB128. It's a basically a common length-prefixed encoding with an extra subtract added in, so someone has probably figured out an efficient algorithm. It might be slightly more instructions than s…
It can't be done, because the next bytes are dependent upon the first byte (which only works in limited circumstances, and where you have constant spacing between the values). ULEB128 works in SIMD because there's only one dependent bit per byte, so you can speculatively decode and then correct later cheaply. Bijou requires you to check the first byte and then branch based on the value using all 8 bits in the decisio…
Right, I think we have a slightly different definition of SIMD: You mean byte-parallel, I mean "doable with SIMD instructions". I also didn't imply the performance would be better than other methods...
Even though decoding the lengths must be serial (since's there's no unambiguous way to differentiate a tag and data byte), it's still doable within the wider SIMD registers, so there's some theoretical efficiency gain to be had (depending on the shape of the data).
On a general note, the continuation bit and prefix byte forms are equivalent, you just broadcast the prefix byte and compare against an increasing vector to convert it to a mask. Yeah, there's probably more fiddly SIMD if there are multiple prefixes in the register, but doable (it's just not byte-parallel, you eg. unroll the serial decode loop 8 times or whatever your maximum output byte width is, and mask out).
Simplified:
// Just maps a byte to its position in the register
__m128i idx = _mm_setr_epi8(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15);
// Broadcast the prefix
__m128i nn = _mm_set1_epi8((char)prefix_byte);
// Get applicable locations: prefix_byte contains the length, if byte_pos Re: Bijou64: A variable-length integer encoding
#55I'm surprised there's no mention in the post or here about SQLite's varint encoding. Not that it would necessarily satisfy the constraints, but it's one of the most used varint implementations.
It's not terribly fast. It's faster than LEB128 but not as fast as vu128 (at least according to https://github.com/Jiboo/varint_benchmark )
The post says the purpose of exploring this space (which is a fun one) wasn't speed, but representation. The speed gain was an added value.
I'm not saying SQLite's varint implementation is ideal for every application. It's just an implementation that is one of the most used implementations, if not the most (I'd bet it is by a large margin though). It just seemed like a missed opportunity to compare it with the implementation they landed on.
EDIT: Just wanted to add, thanks for sharing that link. Interesting!
Re: Bijou64: A variable-length integer encoding
#56I love the random hyperlink underlines on that page
Credit to Roman Komarov who came up with the approach [1], and Todd Matthews [2] who made the art assets.
1: https://kizu.dev/svg-linked-parameters-workaround/ 2: https://www.seaofclouds.com
Re: Bijou64: A variable-length integer encoding
#57Earlier quoted context omitted.
It can't be done, because the next bytes are dependent upon the first byte (which only works in limited circumstances, and where you have constant spacing between the values). ULEB128 works in SIMD because there's only one dependent bit per byte, so you can speculatively decode and then correct later cheaply. Bijou requires you to check the first byte and then branch based on the value using all 8 bits in the decisio…
Right, I think we have a slightly different definition of SIMD: You mean byte-parallel, I mean "doable with SIMD instructions". I also didn't imply the performance would be better than other methods... Even though decoding the lengths must be serial (since's there's no unambiguous way to differentiate a tag and data byte), it's still doable within the wider SIMD registers, so there's some theoretical efficiency gain…
Yeah, sorry, I didn't say that very well. Single value decoding of Bijou values is of course trivial in SIMD, but the performance benefits of SIMD come from deterministic boundaries across a window. ULEB128's continuation bit is fixed position, so it's data independent. One pmovmskb gives you every boundary in the window.
Interleaved Bijou has no such signal (tag and payload bytes both span 0x00–0xFF), so finding the boundaries is a dependent per-value walk with no opportunities for parallelism.
Re: Bijou64: A variable-length integer encoding
#58I researched many different varint encodings for a GraphQL-specific binary format (resulting in Argo: https://github.com/msolomon/argo ). I ended up choosing protobuf-style zig-zag varints, but I also found these interesting:
vu128: https://john-millikin.com/vu128-efficient-variable-length-in...
metric/imperial varint: https://dcreager.net/2021/03/a-better-varint/
vectorizing VByte: https://arxiv.org/abs/1503.07387
Re: Bijou64: A variable-length integer encoding
#59Earlier quoted context omitted.
Right, I think we have a slightly different definition of SIMD: You mean byte-parallel, I mean "doable with SIMD instructions". I also didn't imply the performance would be better than other methods... Even though decoding the lengths must be serial (since's there's no unambiguous way to differentiate a tag and data byte), it's still doable within the wider SIMD registers, so there's some theoretical efficiency gain…
Yeah, sorry, I didn't say that very well. Single value decoding of Bijou values is of course trivial in SIMD, but the performance benefits of SIMD come from deterministic boundaries across a window. ULEB128's continuation bit is fixed position, so it's data independent. One pmovmskb gives you every boundary in the window. Interleaved Bijou has no such signal (tag and payload bytes both span 0x00–0xFF), so finding the…
There's still speculation though - if eg. most values are of 1 or 2-byte length, you can speculate that any control-valued byte is actually control. You can even do a compensation pass to try to fix some amount of mis-speculations, and then bomb out if that fails.
With that, it's mostly byte-parallel (though data-dependent as I mentioned).
Re: Bijou64: A variable-length integer encoding
#60This reminded me of ISO 7816-4 BER-TLV encodings, which uses the format defined in ISO/IEC 8825-1 (ASN.1 related spec). Length integer values of 0-127 are encoded in 1 byte. If the high bit is set, then the first 7 bits tell you the number of subsequent octets. So there's no offsetting involved, making it slightly less compact, but also dead simple.
EDIT: BUT, BER-TLV does permit overlong encodings. And I once found and reported a Yubikey 4 bug related to this. My source code comment for the workaround:
-- The Yubikey 4 has an off-by-one bug which
-- declares tag length of 255 (for the 0x53 outer
-- tag of a certficate DO) when there are only 254
-- bytes remaining in the reply. The reply is
-- chained across two packets, but the off-by-one is
-- probably related to the over-long encoded length
-- (0x82 0x00 0xff instead of 0x81 0xff).
--
-- [snip packet captures]
--
-- Yubico's ykpiv_fetch_object function in ykpiv.c
-- (confirmed 1.4.3-1.5.0) contains a read (memmove)
-- overflow when the declared inner BER-TLV length
-- (of the 0x53 tag) is longer than what was
-- received over the wire. That makes Yubico's
-- library oblivious to the issue. Relatedly, the
-- set_length function has an off-by-one bug (length
--