7 ms·

If you want to see some crazy C code, check out this file from the GitHub repo: https://github.com/lzfse/lzfse/blob/master/src/lzvn_encode_base.c https://github

If you want to see some crazy C code, check out this file from the GitHub repo: https://github.com/lzfse/lzfse/blob/master/src/lzvn_encode_base.c https://github.com/lzfse/lzfse/blob/master/src/lzvn_encode_b...

ghayes 10y ago
It looks like it was run through a Javascript minifier.
drinchev 10y ago
Excerpt from the link : if (D == D_prev) { if (L == 0) { *q++ = 0xF0 + (x + 3); // XM! } else { *q++ = (L << 6) + (x << 3) + 6; // LLxxx110 } *(uint32_t *)q = literal; q += L; // non-aligned access OK } else if (D < 2048 - 2 * 256) { // Short dist D>>8 in 0..5 *q++ = (D >> 8) + (L << 6) + (x << 3); // LLxxxDDD *q++ = D & 0xFF; *(uint32_t *)q = literal; q += L; // non-aligned access OK } else if (D >= (1 << 14) || M == 0 || (x + 3) + M > 34) { // Long dist *q++ = (L << 6) + (x << 3) + 7; *(uint16_t *)q = D; q += 2; // non-aligned access OK *(uint32_t *)q = literal; q += L; // non-aligned access OK } else { // Medium distance x += M; M = 0; *q++ = 0xA0 + (x >> 2) + (L << 3); *(uint16_t *)q = D << 2 | (x & 3); q += 2; // non-aligned access OK *(uint32_t *)q = literal; q += L; // non-aligned access OK }
- barsonme 10y ago
  Blows my mind that people can come up with this stuff. I'm assuming they came up with the mathematical proofs first and translated that into code, so that has something to do with it, correct? It looks a lot like some crypto algorithms which are a nearly direct translation of the mathematical formulas. It's not that it's incredibly difficult to follow, but it's just very "math like".
  - lokedhs 10y ago
    That is my experience. Maths people are not renowned for their ability to write readable or maintainable code. I recently needed an implementation of the Simplex Noise algorithm (that I could port to Common Lisp). I ended up using this one, which works but the code certainly does nothing to help understanding: https://github.com/josephg/noisejs/blob/master/perlin.js https://github.com/josephg/noisejs/blob/master/perlin.js Note that the Javscript implementation is also a port from another language (whose implementation I have failed to find).
    - goldenkey 10y ago
      Seems pretty well commented. There are definitely worse examples. I think you are underestimating the amount of temporary calculations that most mathematical formulas or algorithms require. It's actually a good thing to see so many vars because the variable names combined with the comments make more sense. Any js packer will most certainly get rid of the redundancy of memory allocations, so I'd say the superfluous var style is harmless.
      - josephg 10y ago
        When I wrote it I ran that JS code through several rounds of benchmarking to try and eke out some more performance. One of the tweaks I tried was collapsing all the calculations together to use fewer variables to see if that would make it faster. Performance was totally unchanged either way. Looks like V8's optimizer eats those vars for breakfast.
        jcranmer 10y ago
        In general, at the optimization IR level of any decent compiler or JIT, most straight-line code gets reduced into some form of expression DAG for common subexpression elimination and other similar optimizations, meaning that var x = a + b; call(x + c); and call(a + b + c); would be literally indistinguishable.
    - TULPU 10y ago
- ec109685 10y ago
  It's code like this that has an exploit several years in the future given an edge case that is hard to fathom
  - addicted 10y ago
    The variable names hardly seem complex to me. D clearly refers to some form of "distance". M is "Medium". L is defined before this snippet of code, but I'd imagine it maps to a concept of Long. And you're left with the variable 'q'. The real issue is that unless you are comfortable, code involving pointer math can get confusing (all the * and + can be confusing, especially since they are such overloaded symbols in C). The single character variable names (especially when we're talking about what is basically code representation of mathematical formulae) is hardly a huge issue.
- willvarfar 10y ago
  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.
- guruz 10y ago
  Browse this snippet with hover overlays and semantic linking: https://code.woboq.org/lzfse/lzfse/src/lzvn_encode_base.c.html#126 https://code.woboq.org/lzfse/lzfse/src/lzvn_encode_base.c.ht...
- joeblau 10y ago
  I feel like the main thing that makes this look crazy is the variable naming and bit shifting. If someone saw this program with descriptive variable names and array operations, it would probably look less daunting.
  - PeCaN 10y ago
    Eh. I feel like long variable names would obscure the algorithm. And bit shifting and array operations aren't interchangeable…. C just tends to look like line noise for numerical algorithms sometimes.
    - joeblau 10y ago
      Yeah that's true; they aren't interchangeable but you can create functions that perform all of the bit shifting operations on arrays; Performance just suffers.
- deleted 10y ago
  [deleted]
- cmiller1 10y ago
  In some of these lines I feel like I'd prefer to see more parenthesis. Sure, I can figure out what is happening here: } else if (D < 2048 - 2 * 256) { but if it were grouped with a few more parenthesis it would take a little less time for me to grok it.
  - jmaygarden 10y ago
    There is a lot to be said for really knowing the order of operations. I write a lot of C code and this looks very clear to me. More parenthesis would just add noise from my perspective.
- etatoby 10y ago
  That looks like a host of buffer overflow vulnerabilities waiting to happen. I think I'll stick with zlib.
gigatexal 10y ago
I wonder why they use goto statements instead of just returning q1 like the statement evaluates to.
- gakada 10y ago
  It's more DRY.
- Pica_soO 10y ago
  No function call overhead. Makes sense as long as you stay in the same state-machine. This thing doesn't have to be pretty. It has to be fast. Who cares for any oo-written implementation that takes half a hour to do the same job?
  - nodesocket 10y ago
    But there is no function call overhead right? Replacing goto OUT_FULL; with return q1; would seem to be faster right? No need for a goto, just invoke return. What am I missing?
    - valarauca1 10y ago
      There is some. A few register need to be assigned, and everything else gets pushed/copied onto the stack. Then you jump to a location and copy everything back off the stack. This doesn't take many cycles, but it does take some. While a GOTO is just a jump.
      - xxs 10y ago
        the compilers are free to optimize. Creating a stack frame for each function is trivially avoided by inlining (esp. trivial for non-polymorph call sites)
        valarauca1 10y ago
        It depends. In GCC/MSVC will only (attempt to) inline what you mark as inline. Then MSVC has a keyword which forces inlining. Unless you set a flag which tells the compiler to inline what ever it wants. But that being said Microsoft has a non-POSIX x64 ABI designed to allow better in-lining. How inlining works starts to dive pretty deep into the compiler rabbit hole.
venomsnake 10y ago
When a code is rooted deeply in domain, the definition or crazy should take into context is code readable for people in knowledge in the same domain.
vbezhenar 10y ago
I think that there's a scientific paper accompanying that code somewhere. So in order to understand that code one should read the paper and all those names probably just came from paper's algorithms.
saynsedit 10y ago
Undefined type-punning cringes me out. memcpy is your well-defined friend.

ghayes 10y ago

It looks like it was run through a Javascript minifier.

drinchev 10y ago

Excerpt from the link : if (D == D_prev) { if (L == 0) { *q++ = 0xF0 + (x + 3); // XM! } else { *q++ = (L << 6) + (x << 3) + 6; // LLxxx110 } *(uint32_t *)q = literal; q += L; // non-aligned access OK } else if (D < 2048 - 2 * 256) { // Short dist D>>8 in 0..5 *q++ = (D >> 8) + (L << 6) + (x << 3); // LLxxxDDD *q++ = D & 0xFF; *(uint32_t *)q = literal; q += L; // non-aligned access OK } else if (D >= (1 << 14) || M == 0 || (x + 3) + M > 34) { // Long dist *q++ = (L << 6) + (x << 3) + 7; *(uint16_t *)q = D; q += 2; // non-aligned access OK *(uint32_t *)q = literal; q += L; // non-aligned access OK } else { // Medium distance x += M; M = 0; *q++ = 0xA0 + (x >> 2) + (L << 3); *(uint16_t *)q = D << 2 | (x & 3); q += 2; // non-aligned access OK *(uint32_t *)q = literal; q += L; // non-aligned access OK }

barsonme 10y ago
Blows my mind that people can come up with this stuff. I'm assuming they came up with the mathematical proofs first and translated that into code, so that has something to do with it, correct? It looks a lot like some crypto algorithms which are a nearly direct translation of the mathematical formulas. It's not that it's incredibly difficult to follow, but it's just very "math like".
- lokedhs 10y ago
  That is my experience. Maths people are not renowned for their ability to write readable or maintainable code. I recently needed an implementation of the Simplex Noise algorithm (that I could port to Common Lisp). I ended up using this one, which works but the code certainly does nothing to help understanding: https://github.com/josephg/noisejs/blob/master/perlin.js https://github.com/josephg/noisejs/blob/master/perlin.js Note that the Javscript implementation is also a port from another language (whose implementation I have failed to find).
  - goldenkey 10y ago
    Seems pretty well commented. There are definitely worse examples. I think you are underestimating the amount of temporary calculations that most mathematical formulas or algorithms require. It's actually a good thing to see so many vars because the variable names combined with the comments make more sense. Any js packer will most certainly get rid of the redundancy of memory allocations, so I'd say the superfluous var style is harmless.
    - josephg 10y ago
      When I wrote it I ran that JS code through several rounds of benchmarking to try and eke out some more performance. One of the tweaks I tried was collapsing all the calculations together to use fewer variables to see if that would make it faster. Performance was totally unchanged either way. Looks like V8's optimizer eats those vars for breakfast.
      - jcranmer 10y ago
        In general, at the optimization IR level of any decent compiler or JIT, most straight-line code gets reduced into some form of expression DAG for common subexpression elimination and other similar optimizations, meaning that var x = a + b; call(x + c); and call(a + b + c); would be literally indistinguishable.
  - TULPU 10y ago
ec109685 10y ago
It's code like this that has an exploit several years in the future given an edge case that is hard to fathom
- addicted 10y ago
  The variable names hardly seem complex to me. D clearly refers to some form of "distance". M is "Medium". L is defined before this snippet of code, but I'd imagine it maps to a concept of Long. And you're left with the variable 'q'. The real issue is that unless you are comfortable, code involving pointer math can get confusing (all the * and + can be confusing, especially since they are such overloaded symbols in C). The single character variable names (especially when we're talking about what is basically code representation of mathematical formulae) is hardly a huge issue.
willvarfar 10y ago
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.
guruz 10y ago
Browse this snippet with hover overlays and semantic linking: https://code.woboq.org/lzfse/lzfse/src/lzvn_encode_base.c.html#126 https://code.woboq.org/lzfse/lzfse/src/lzvn_encode_base.c.ht...
joeblau 10y ago
I feel like the main thing that makes this look crazy is the variable naming and bit shifting. If someone saw this program with descriptive variable names and array operations, it would probably look less daunting.
- PeCaN 10y ago
  Eh. I feel like long variable names would obscure the algorithm. And bit shifting and array operations aren't interchangeable…. C just tends to look like line noise for numerical algorithms sometimes.
  - joeblau 10y ago
    Yeah that's true; they aren't interchangeable but you can create functions that perform all of the bit shifting operations on arrays; Performance just suffers.
deleted 10y ago
[deleted]
cmiller1 10y ago
In some of these lines I feel like I'd prefer to see more parenthesis. Sure, I can figure out what is happening here: } else if (D < 2048 - 2 * 256) { but if it were grouped with a few more parenthesis it would take a little less time for me to grok it.
- jmaygarden 10y ago
  There is a lot to be said for really knowing the order of operations. I write a lot of C code and this looks very clear to me. More parenthesis would just add noise from my perspective.
etatoby 10y ago
That looks like a host of buffer overflow vulnerabilities waiting to happen. I think I'll stick with zlib.

gigatexal 10y ago

I wonder why they use goto statements instead of just returning q1 like the statement evaluates to.

gakada 10y ago
It's more DRY.
Pica_soO 10y ago
No function call overhead. Makes sense as long as you stay in the same state-machine. This thing doesn't have to be pretty. It has to be fast. Who cares for any oo-written implementation that takes half a hour to do the same job?
- nodesocket 10y ago
  But there is no function call overhead right? Replacing goto OUT_FULL; with return q1; would seem to be faster right? No need for a goto, just invoke return. What am I missing?
  - valarauca1 10y ago
    There is some. A few register need to be assigned, and everything else gets pushed/copied onto the stack. Then you jump to a location and copy everything back off the stack. This doesn't take many cycles, but it does take some. While a GOTO is just a jump.
    - xxs 10y ago
      the compilers are free to optimize. Creating a stack frame for each function is trivially avoided by inlining (esp. trivial for non-polymorph call sites)
      - valarauca1 10y ago
        It depends. In GCC/MSVC will only (attempt to) inline what you mark as inline. Then MSVC has a keyword which forces inlining. Unless you set a flag which tells the compiler to inline what ever it wants. But that being said Microsoft has a non-POSIX x64 ABI designed to allow better in-lining. How inlining works starts to dive pretty deep into the compiler rabbit hole.

venomsnake 10y ago

When a code is rooted deeply in domain, the definition or crazy should take into context is code readable for people in knowledge in the same domain.

vbezhenar 10y ago

I think that there's a scientific paper accompanying that code somewhere. So in order to understand that code one should read the paper and all those names probably just came from paper's algorithms.

saynsedit 10y ago

Undefined type-punning cringes me out. memcpy is your well-defined friend.