3 ms·

I've never seen this code base before, but this makes straightforward sense to me as I do keep my hand in with compression software, and I don't anticipate othe

I've never seen this code base before, but this makes straightforward sense to me as I do keep my hand in with compression software, and I don't anticipate others who works with compression algorithms in general would have any trouble. It looks just like the style of code in all the other fast LZ codebases. They are all in this style. The "non-aligned access OK" comment litter is presumably to silence an LLVM performance sanitizer.

nabla9 10y ago
When implementing complex algorithm, this kind of code is usually easiest to understand. When you look at the code, you use the paper that describes the algorithm as documentation. Using same short one letter variable names in the code and paper makes understanding much easier. The thing I hate most is when the the paper uses 1-based numbering and the programming language uses 0-based numbering. We should settle for 0-based numbering when describing algorithms.
- eru 10y ago
  Arithmetic coding often looks just as dense, because C is not a good vehicle to describe algorithms. Look at eg https://www.cs.ox.ac.uk/jeremy.gibbons/publications/arith.pdf https://www.cs.ox.ac.uk/jeremy.gibbons/publications/arith.pd... to see a cleaner alternative. (This is about describing algorithms in papers. Optimizing for performance after the big-O has been taken care of is a different matter.)
- catwell 10y ago
  Or use 1-based programming languages :) I have implemented several algorithms from papers in Lua and that played in my favor more than once.
PeCaN 10y ago
I agree. The only questionable part is the stuff like *(uint16_t *)q = D; q += 2; // non-aligned access OK *(uint32_t *)q = literal; instead of memcpy(q, &D, sizeof(uint16_t)); q += 2; // non-aligned access OK memcpy(q, &literal, sizeof(uint32_t)); which is better defined behavior (i.e. doesn't violate -fstrict-aliasing) and possibly faster.
- legulere 10y ago
  Why not test it and do a pull request?
  - PeCaN 10y ago
    Well… it's honestly because I don't give a shit about LZFSE and Apple can fix their own code. But I could also say that I'm lazy and it's not a big deal anyway.
acqq 10y ago
I've also never seen that code but it's very readable for me, just based on the snippet. It's supposed to encode the information tuple and store it as the next entry of variable length on the position pointed by q. Every tuple ends with the 32-bit literal, but what comes before depends on the size of the displacement, and of course, smaller displacements need less bytes.

nabla9 10y ago

When implementing complex algorithm, this kind of code is usually easiest to understand. When you look at the code, you use the paper that describes the algorithm as documentation. Using same short one letter variable names in the code and paper makes understanding much easier. The thing I hate most is when the the paper uses 1-based numbering and the programming language uses 0-based numbering. We should settle for 0-based numbering when describing algorithms.

eru 10y ago
Arithmetic coding often looks just as dense, because C is not a good vehicle to describe algorithms. Look at eg https://www.cs.ox.ac.uk/jeremy.gibbons/publications/arith.pdf https://www.cs.ox.ac.uk/jeremy.gibbons/publications/arith.pd... to see a cleaner alternative. (This is about describing algorithms in papers. Optimizing for performance after the big-O has been taken care of is a different matter.)
catwell 10y ago
Or use 1-based programming languages :) I have implemented several algorithms from papers in Lua and that played in my favor more than once.

PeCaN 10y ago

I agree. The only questionable part is the stuff like *(uint16_t *)q = D; q += 2; // non-aligned access OK *(uint32_t *)q = literal; instead of memcpy(q, &D, sizeof(uint16_t)); q += 2; // non-aligned access OK memcpy(q, &literal, sizeof(uint32_t)); which is better defined behavior (i.e. doesn't violate -fstrict-aliasing) and possibly faster.

legulere 10y ago
Why not test it and do a pull request?
- PeCaN 10y ago
  Well… it's honestly because I don't give a shit about LZFSE and Apple can fix their own code. But I could also say that I'm lazy and it's not a big deal anyway.

acqq 10y ago

I've also never seen that code but it's very readable for me, just based on the snippet. It's supposed to encode the information tuple and store it as the next entry of variable length on the position pointed by q. Every tuple ends with the 32-bit literal, but what comes before depends on the size of the displacement, and of course, smaller displacements need less bytes.