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

Libbbf: Bound Book Format, A high-performance container for comics and manga

github.com

Post reply on HN
Print view View original

51–60 of 66 posts

Re: Libbbf: Bound Book Format, A high-performance container for comics and manga

#51

Post by minitech »

zigzag312 wrote: post #49
jmillikin wrote: post #43

Earlier quoted context omitted.

> It seems that JPEG can be decoded on the GPU [1] [2] Sure, but you wouldn't want to. Many algorithms can be executed on a GPU via CUDA/ROCm, but the use cases for on-GPU JPEG/PNG decoding (mostly AI model training? maybe some sort of giant megapixel texture?) are unrelated to anything you'd use CBZ for. For a comic book the performance-sensitive part is loading the current and adjoining pages, which can be done fas…

> which can be done fast enough to appear instant on the CPU Big scanned PDFs can be problfrom more efficient processing (if it had HW support for such technique) > Your link shows CRC32 at 7963.20 MiB/s (~7.77 GiB/s) which indicates it's either very old or isn't measuring pure CRC32 throughput It may not be fastest implementation of CRC32, but it's also done on old Ryzen 5 3350G 3.6GHz. Below the table are results d…

> What would be an issue, if they used 128 bit xxhash instead of 128 bit cryptographic hash like they do now (if we assume we don't need to protection from tampering)?

malicious block hash collisions where the colliding block was introduced by some way other than tampering (e.g. storing a file created by someone else)

Re: Libbbf: Bound Book Format, A high-performance container for comics and manga

#52

Post by rovr138 »

zigzag312 wrote: post #31
sedatk wrote: post #15

> Footer indexed So, like ZIP? > Uses XXH3 for integrity checks I don’t think XXH3 is suitable for that purpose. It’s not cryptographically secure and designed mostly for stuff like hash tables (e.g. relatively small data).

Why would it need to be cryptographically secure for this use case?

If the data is big enough, collisions. Right?

Re: Libbbf: Bound Book Format, A high-performance container for comics and manga

#53

Post by minitech »

zigzag312 wrote: post #45
myrmidon wrote: post #41

Earlier quoted context omitted.

Maybe the CRC32 implementations in the smasher suite just aren't that fast? [1] claims 15 GB/s for the slowest implementation (Chromium) they compared (all vectorized). > The 32 bit hash of CRC32 is too low for file checksums. xxhash is definitely an improvement over CRC32. Why? What kind of error rate do you expect, and what kind of reliability do you want to achieve? Assumptions that would lead to a >32bit checksum…

From SMHasher test results quality of xxhash seems higher. It has less bias / higher uniformity that CRC. What bothers me with probability calculations, is that they always assume perfect uniformity. I've never seen any estimates how bias affects collision probability and how to modify the probability formula to account for non-perfect uniformity of a hash function.

Uniformity isn’t directly important for error detection. CRC-32 has the nice property that it’s guaranteed to detect all burst errors up to 32 bits in size, while hashes do that with probability at best 2^−b of course. (But it’s valid to care about detecting larger errors with higher probability, yes.)

Re: Libbbf: Bound Book Format, A high-performance container for comics and manga

#54

Post by zigzag312 »

fc417fc802 wrote: post #46
zigzag312 wrote: post #42

Earlier quoted context omitted.

I've seen few arguments that with the amount of data we have today the 2^(32-1) chance can happen, but I can't vouch their calculations were done correctly. Readme in SMHasher test suite also seems to indicate that 32 bits might be too few for file checksums: "Hash functions for symbol tables or hash tables typically use 32 bit hashes, for databases, file systems and file checksums typically 64 or 128bit, for crypto…

That's vaguely describing common practices, not what's actually necessary or why. It also doesn't address my note that the purpose of the hash is important. Are "file systems" and "file checksums" referring to globally unique handles, content addressed tables, detection of bitrot, or something else? For detecting file corruption the amount of data alone isn't the issue. Rather what matters is the rate at which corrup…

It depends on how you calculate statistics. If you are designing a file format that over the lifetime of the format hundreds of millions of user will use (storing billions of files), what are the chances that 32 bits checksum won't be able to catch at least one corruption? During transfer over unstable wireless internet connection, storage on cheap flash drive, poor HDD with a higher error rate, unstable RAM etc. We want to avoid data corruption if we can even in less then ideal conditions. Cost of going from 32 bit to 64 bit hashes is very small.

Re: Libbbf: Bound Book Format, A high-performance container for comics and manga

#55

Post by zigzag312 »

minitech wrote: post #51
zigzag312 wrote: post #49

Earlier quoted context omitted.

> which can be done fast enough to appear instant on the CPU Big scanned PDFs can be problfrom more efficient processing (if it had HW support for such technique) > Your link shows CRC32 at 7963.20 MiB/s (~7.77 GiB/s) which indicates it's either very old or isn't measuring pure CRC32 throughput It may not be fastest implementation of CRC32, but it's also done on old Ryzen 5 3350G 3.6GHz. Below the table are results d…

> What would be an issue, if they used 128 bit xxhash instead of 128 bit cryptographic hash like they do now (if we assume we don't need to protection from tampering)? malicious block hash collisions where the colliding block was introduced by some way other than tampering (e.g. storing a file created by someone else)

That's a good example. Thanks! It would be kind of an indirect tampering method.

Re: Libbbf: Bound Book Format, A high-performance container for comics and manga

#56

Post by usefulcat »

toyg wrote: post #36
panja wrote: post #19

Earlier quoted context omitted.

If you read the reddit thread, it was coded by hand then only bug checked with ai.

It was benchmarked with AI. Benchmarks being the main reason for this thing existing...

After reading the reddit comments, it looks like a primary problem is that the author doesn't (didn't?) understand how to benchmark it correctly. Like comparing the time to mmap() a file with the time to actually read the same file. Not at all the same thing.

For example: https://old.reddit.com/r/selfhosted/comments/1qi64pr/i_got_i...

Re: Libbbf: Bound Book Format, A high-performance container for comics and manga

#57

Post by zigzag312 »

minitech wrote: post #53
zigzag312 wrote: post #45

Earlier quoted context omitted.

From SMHasher test results quality of xxhash seems higher. It has less bias / higher uniformity that CRC. What bothers me with probability calculations, is that they always assume perfect uniformity. I've never seen any estimates how bias affects collision probability and how to modify the probability formula to account for non-perfect uniformity of a hash function.

Uniformity isn’t directly important for error detection. CRC-32 has the nice property that it’s guaranteed to detect all burst errors up to 32 bits in size, while hashes do that with probability at best 2^−b of course. (But it’s valid to care about detecting larger errors with higher probability, yes.)

> Uniformity isn’t directly important for error detection.

Is there any proof of this? I'm interested in reading more about it.

> detect all burst errors up to 32 bits in size

What if errors are not consecutive bits?

Re: Libbbf: Bound Book Format, A high-performance container for comics and manga

#59

Post by minitech »

zigzag312 wrote: post #57
minitech wrote: post #53

Earlier quoted context omitted.

Uniformity isn’t directly important for error detection. CRC-32 has the nice property that it’s guaranteed to detect all burst errors up to 32 bits in size, while hashes do that with probability at best 2^−b of course. (But it’s valid to care about detecting larger errors with higher probability, yes.)

> Uniformity isn’t directly important for error detection. Is there any proof of this? I'm interested in reading more about it. > detect all burst errors up to 32 bits in size What if errors are not consecutive bits?

There’s a whole field’s worth of really cool stuff about error correction that I wish I knew a fraction of enough to give reading recommendations about, but my comment wasn’t that deep – it’s just that in hashes, you obviously care about distribution because that’s almost the entire point of non-cryptographic hashes, and in error correction you only care that x ≠ y implies f(x) ≠ f(y) with high probability, which is only directly related in the obvious way of making use of the output space (even though it’s probably indirectly related in some interesting subtler ways).

E.g. f(x) = concat(xxhash32(x), 0xf00) is just as good at error detection as xxhash32 but is a terrible hash, and, as mentioned, CRC-32 is infinitely better at detecting certain types of errors than any universal hash family.

Re: Libbbf: Bound Book Format, A high-performance container for comics and manga

#60

Post by fc417fc802 »

zigzag312 wrote: post #54
fc417fc802 wrote: post #46

Earlier quoted context omitted.

That's vaguely describing common practices, not what's actually necessary or why. It also doesn't address my note that the purpose of the hash is important. Are "file systems" and "file checksums" referring to globally unique handles, content addressed tables, detection of bitrot, or something else? For detecting file corruption the amount of data alone isn't the issue. Rather what matters is the rate at which corrup…

It depends on how you calculate statistics. If you are designing a file format that over the lifetime of the format hundreds of millions of user will use (storing billions of files), what are the chances that 32 bits checksum won't be able to catch at least one corruption? During transfer over unstable wireless internet connection, storage on cheap flash drive, poor HDD with a higher error rate, unstable RAM etc. We…

No, it doesn't "depend on how you calculate statistics". Or rather you are not asking the right question. We do not care if a different person suffers a false negative. The question is if you, personally, are likely to suffer a false negative. In other words, will any given real world deployment of the solution be expected to suffer from an unacceptably high rate of false negatives?

Answering that requires figuring out two things. The sort of real world deployment you're designing for and what the acceptable false negative rate is. For an extremely conservative lower bound suppose 1 error per TiB per year and suppose 1000 TiB of storage. That gives a 99.99998% success rate for any given year. That translates to expecting 1 false negative every 4 million years.

I don't know about you but I certainly don't have anywhere near a petabyte of data, I don't suffer corruption at anywhere near a rate of 1 event per TiB per year, and I'm not in the business of archiving digital data on a geological timeframe.

32 bits is more than fit for purpose.

Post reply on HN