Feature Request: LEB128 integers

[willtemperley]

It would be great if there was a way to parse LEB128 integers. These are very common in formats like Parquet (which I'm building a parser for), and Protobuf.

extension UInt64 {
    
    public init(parsing input: inout ParserSpan) throws {
        
        var value: UInt64 = 0
        var shift: UInt64 = 0
        
        while true {
            guard shift <= 63 else { // 63 is the max shift for a UInt64
                // The varint is too long to fit in a UInt64.
                throw BinaryParsing.error("Varint too long to fit in UInt64")
            }
            
            let byte = try UInt8(parsingLittleEndian: &input, byteCount: 1)
            
            value |= UInt64(byte & 0x7f) << shift
            
            if (byte & 0x80) == 0 {
                self = value
                return
            }
            
            shift += 7
        }
    }
}

[stephentyrone]

Agreed that this makes sense to have. Would you be interested in putting together a PR for it? Nate or I can help out as needed.

[willtemperley]

I'd be happy to put together a pull request. I've made a start in my fork.

So for the tests, I'll have to add a LEB128 encoder to generate byte arrays for each integer the fuzzer comes up with I guess.

Then for Single, Multi and PlatformWidth integers I'll need a block doing:

let parsed = try lePlain.withParserSpan { try T(parsingLEB128: &$0) }
#expect(parsed == number)

If that sounds reasonable?

[natecook1000]

Sounds great - thanks for working on this!

[willtemperley]

I'm thinking my API design in #31 is not ideal.

For example, using Int(parsingLEB128:) to parse unsigned LEB128 is an error. The parser will probably run, but may or may not give the correct result.

I'm thinking using separate initialisers parsingULEB128 and parsingSLEB128 would make more sense, because really they are different encodings. Second, the unsigned version would be faster.

How about:

extension FixedWidthInteger {
  public init(parsingULEB128 input: inout ParserSpan) throws(ParsingError) {
    // All unsigned LEB128 can decode correctly to an unsigned integer of sufficient width
  }
}

extension SignedInteger {
  public init(parsingSLEB128 input: inout ParserSpan) throws(ParsingError) {
  }
}

[stephentyrone]

That sounds about right; my recollection is that signed LEB encodings are relatively uncommon compared to unsigned (though I may be mistaken). If so, we might have parsingLEB128 (unsigned) and parsingSignedLEB128 as labels.

It may also be desirable to be able to decode a signed LEB encoding into an unsigned integer (throwing if it's negative), but I'll defer to Nate on that point.

[natecook1000]

For the existing integer parsers, the way you choose signedness is in your selection of the parsing type, or the storage type when performing a "converting" parse.

UInt16(parsingBigEndian: &input, byteCount: 3)        // Parses an unsigned 3-byte integer
Int16(parsingBigEndian: &input, byteCount: 3)         // Parses an signed 3-byte integer

Int(parsing: &input, storedAsBigEndian: UInt32.self)  // Parses an unsigned 4-byte integer
Int(parsing: &input, storedAsBigEndian: Int32.self)   // Parses an signed 4-byte integer

The first form, where the signedness is implicit in the selected destination type, still makes sense with the LEB128 format. The second form, which lets you choose the signedness separately from the destination type, doesn't. What would you think about these? The "standard" version would use the destination type's signedness, and then signed types could have a separate "unsigned" parser and unsigned types could have a "signed" parser.

extension FixedWidthInteger {
  public init(parsingLEB128 input: inout ParserSpan) throws(ParsingError) {
    // Parsing algorithm corresponds with Self.isSigned
  }
}

extension FixedWidthInteger & SignedInteger {
  public init(parsingUnsignedLEB128 input: inout ParserSpan) throws(ParsingError) {}
}

extension FixedWidthInteger & UnsignedInteger {
  public init(parsingSignedLEB128 input: inout ParserSpan) throws(ParsingError) {}
}

Do both of those additional parsers make sense to include?

[willtemperley]

I think that might be good for API discovery. If I saw parsingSignedLEB128 on a signed type, I'd probably look for parsingUnsignedLEB128 rather than parsingLEB128.

However we can't detect the encoding at runtime, so I don't think we can have this:

extension FixedWidthInteger {
  public init(parsingLEB128 input: inout ParserSpan) throws(ParsingError) {
    // Parsing algorithm corresponds with Self.isSigned
  }
}

For example, if I was parsing a length-value record, I might want to get an Int from the stream to pass to the next parsing step. If the stream is unsigned LEB128 and the parsing algorithm corresponds with Self.isSigned, this will attempt to decode records of negative length in many cases:

extension [UInt8] {
    init(parsingLengthValueRecord input: inout ParserSpan) throws {
        let len = try Int(parsingLEB128: &input)
        self = try .init(parsing: &input, byteCount: len)
    }
}

e.g. the integers 64 to 127 encoded in unsigned LEB128, but parsed with the signed-LEB128 algorithm would yield -64 to -1 becuase the sign bit is set.

I only know this because I was bitten by this exact issue. The tests for a Thrift parser were passing using toy record sizes, but the parser was breaking on real data.

Of course a user could do let len = try UInt(parsingLEB128: &input) but I think one of the nice features of this library is being able to choose exactly what the parsed type will be.

[willtemperley]

Great this has been merged!

How about making it explicit that the type determines the encoding consumed?
For example something like this in the doc comment:

\\\ The encoding variant is determined by the selected destination type.