4 ms·

> twenty five thousand lines of pure C not counting CMake files. ... Keep in mind this is also 31 years of cruft and lord knows what. Plan 9 gzip is 738 lines

> twenty five thousand lines of pure C not counting CMake files. ... Keep in mind this is also 31 years of cruft and lord knows what. Plan 9 gzip is 738 lines total: gzip.c 217 lines gzip.h 40 lines zip.c 398 lines zip.h 83 lines Even the zipfs file server that mounts zip files as file systems is 391 lines. edit - post a link to said code: https://github.com/9front/9front/tree/front/sys/src/cmd/gzip https://github.com/9front/9front/tree/front/sys/src/cmd/gzip > ... (and whenever working with C always keep in mind that C stands for CVE). Sigh.

tyingq 7mo ago
His also omits CRC, which is part of the 25k lines, no --fast/--best/etc, missing some output formats, and so on. I'm sure the 25k includes a lot of bloat, but the comparison is odd. Comparing to your list would make much more sense.
- kibwen 7mo ago
  I would expect a CRC to add a negligible number of lines of code. The reason that production-grade decompressors are tens of thousands of LOC is likely attributable to extreme manual optimization. For example, I wouldn't be surprised if a measurable fraction of those lines are actually inline assembly.
  - tyingq 7mo ago
    Yes, there's subdirs with language bindings for many non-C langs, an examples folder with example C code, win32 specific C code, test code, etc. More reasons it's an odd comparison.
  - nayuki 7mo ago
    True. A most basic CRC implementation is about 7 lines of code: (presented in Java to avoid some C/C++ footguns) int crc32(byte[] data) { int crc = ~0; for (byte b : data) { crc ^= b & 0xFF; for (int i = 0; i < 8; i++) crc = (crc >>> 1) ^ ((crc & 1) * 0xEDB88320); } return ~crc; } Or smooshed down slightly (with caveats): int crc32(byte[] data) { int crc = ~0; for (int i = 0; i < data.length * 8; i++) { crc ^= (data[i / 8] >> (i % 8)) & 1; crc = (crc >>> 1) ^ ((crc & 1) * 0xEDB88320); } return ~crc; } But one reason that many CRC implementations are large is because they include a pre-computed table of 256× 32-bit constants so that one byte can processed at a time. For example: https://github.com/madler/zlib/blob/7cdaaa09095e9266dee21314599a9258db53685e/crc32.h https://github.com/madler/zlib/blob/7cdaaa09095e9266dee21314...
    - xxs 7mo ago
      That's java code, though... bit weird, esp. i % 8 (which is just i & 7). The compiler should be able to optimize it since 'i' is guaranteed to be non-negative, still awkward. Java CRC32 nowadays uses intrinsics and avx128 for crc32.
    - kevin_thibedeau 7mo ago
      With C++20 you can use consteval to compute the table(s) at compile time from template parameters.
  - ack_complete 7mo ago
    Doesn't need to be inline assembly, just pre-encoded lookup tables and intrinsics-based vectorized CRC alone will add quite a lot of code. Most multi-platform CRC algorithms tend to have at least a few paths for byte/word/dword at a time, hardware CRC, and hardware GF(2) multiply. It's not really extreme optimization, just better algorithms to match better hardware capabilities. The Huffman decoding implementation is also bigger in production implementations for both speed and error checking. Two Huffman trees need to be exactly complete except in the special case of a single code, and in most cases they are flattened to two-level tables for speed (though the latest desktop CPUs have enough L1 cache to use single-level). Finally, the LZ copy typically has special cases added for using wider than byte copies for non-overlapping, non-wrapping runs. This is a significant decoding speed optimization.
- fullstop 7mo ago
  gzip also contains a significant amount of compatibility code for different platforms.
- xxs 7mo ago
  Crc32 can be written in handful lines of code. Although it'd be better to use the vector instruction set - e.g. AVX when available.
bboozzoo 7mo ago
You forgot to include https://github.com/9front/9front/tree/front/sys/src/libflate https://github.com/9front/9front/tree/front/sys/src/libflate which gzip is built around, which brings it closer to 10k lines.
- carlos256 7mo ago
  Interesting, the decompressor in Jdeflate is around 4k LoC. https://github.com/Jpn666/jdeflate https://github.com/Jpn666/jdeflate
- commandlinefan 7mo ago
  I wrote a standalone gzip decompressor in about 500 lines of code (including comments, with braces on the next line), with no dependencies at all: https://commandlinefanatic.com/cgi-bin/showarticle.cgi?article=art001 https://commandlinefanatic.com/cgi-bin/showarticle.cgi?artic...

tyingq 7mo ago

His also omits CRC, which is part of the 25k lines, no --fast/--best/etc, missing some output formats, and so on. I'm sure the 25k includes a lot of bloat, but the comparison is odd. Comparing to your list would make much more sense.

kibwen 7mo ago
I would expect a CRC to add a negligible number of lines of code. The reason that production-grade decompressors are tens of thousands of LOC is likely attributable to extreme manual optimization. For example, I wouldn't be surprised if a measurable fraction of those lines are actually inline assembly.
- tyingq 7mo ago
  Yes, there's subdirs with language bindings for many non-C langs, an examples folder with example C code, win32 specific C code, test code, etc. More reasons it's an odd comparison.
- nayuki 7mo ago
  True. A most basic CRC implementation is about 7 lines of code: (presented in Java to avoid some C/C++ footguns) int crc32(byte[] data) { int crc = ~0; for (byte b : data) { crc ^= b & 0xFF; for (int i = 0; i < 8; i++) crc = (crc >>> 1) ^ ((crc & 1) * 0xEDB88320); } return ~crc; } Or smooshed down slightly (with caveats): int crc32(byte[] data) { int crc = ~0; for (int i = 0; i < data.length * 8; i++) { crc ^= (data[i / 8] >> (i % 8)) & 1; crc = (crc >>> 1) ^ ((crc & 1) * 0xEDB88320); } return ~crc; } But one reason that many CRC implementations are large is because they include a pre-computed table of 256× 32-bit constants so that one byte can processed at a time. For example: https://github.com/madler/zlib/blob/7cdaaa09095e9266dee21314599a9258db53685e/crc32.h https://github.com/madler/zlib/blob/7cdaaa09095e9266dee21314...
  - xxs 7mo ago
    That's java code, though... bit weird, esp. i % 8 (which is just i & 7). The compiler should be able to optimize it since 'i' is guaranteed to be non-negative, still awkward. Java CRC32 nowadays uses intrinsics and avx128 for crc32.
  - kevin_thibedeau 7mo ago
    With C++20 you can use consteval to compute the table(s) at compile time from template parameters.
- ack_complete 7mo ago
  Doesn't need to be inline assembly, just pre-encoded lookup tables and intrinsics-based vectorized CRC alone will add quite a lot of code. Most multi-platform CRC algorithms tend to have at least a few paths for byte/word/dword at a time, hardware CRC, and hardware GF(2) multiply. It's not really extreme optimization, just better algorithms to match better hardware capabilities. The Huffman decoding implementation is also bigger in production implementations for both speed and error checking. Two Huffman trees need to be exactly complete except in the special case of a single code, and in most cases they are flattened to two-level tables for speed (though the latest desktop CPUs have enough L1 cache to use single-level). Finally, the LZ copy typically has special cases added for using wider than byte copies for non-overlapping, non-wrapping runs. This is a significant decoding speed optimization.
fullstop 7mo ago
gzip also contains a significant amount of compatibility code for different platforms.
xxs 7mo ago
Crc32 can be written in handful lines of code. Although it'd be better to use the vector instruction set - e.g. AVX when available.

bboozzoo 7mo ago

You forgot to include https://github.com/9front/9front/tree/front/sys/src/libflate https://github.com/9front/9front/tree/front/sys/src/libflate which gzip is built around, which brings it closer to 10k lines.

carlos256 7mo ago
Interesting, the decompressor in Jdeflate is around 4k LoC. https://github.com/Jpn666/jdeflate https://github.com/Jpn666/jdeflate
commandlinefan 7mo ago
I wrote a standalone gzip decompressor in about 500 lines of code (including comments, with braces on the next line), with no dependencies at all: https://commandlinefanatic.com/cgi-bin/showarticle.cgi?article=art001 https://commandlinefanatic.com/cgi-bin/showarticle.cgi?artic...