Hacker News Reader

Comment by nodesocket | Hacker News Reader

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_b...

View on HN

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
      }

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.

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.

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.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.)

Or use 1-based programming languages :) I have implemented several algorithms from papers in Lua and that played in my favor more than once.

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.

Why not test it and do a pull request?

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.

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.

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".

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

Note that the Javscript implementation is also a port from another language (whose implementation I have failed to find).

> Maths people are not renowned for their ability to write readable or maintainable code.

I think it's because in that circle of heavy math coding, there are a different set of well-understood abstractions and shortcuts.

It's no different than saying front-end web developers are not writing readable code because they use $(...) instead of elementMatchingSelector(...) or use functions like xhr() instead of xmlHTTPrequest(). Node.js developers don't think twice about the mechanics of callbacks nor to Erlang developers have any mental block about async message semantics.

Each field has a lingo that has evolved over time, and those who have been in a field for longer tend to make more shortcuts because they are manipulating a concept for the 100th time and are well versed in it.

Hey, someone found those noise functions I ported to JS a few years ago!

Sorry for not referencing the original code. The java version I translated from is here: http://webstaff.itn.liu.se/~stegu/simplexnoise/SimplexNoise....

And the paper describing the algorithm is here: http://webstaff.itn.liu.se/~stegu/simplexnoise/simplexnoise....

Glad it was useful to you!

I used that code to create a Common Lisp version, the result is here: https://gist.github.com/lokedhs/d5348c4a221e1436000b

I used it as a base for a map generator for a strategy game. Thanks a lot for the code, it worked perfectly.

It's funny, but nothing helps you understand something better than porting it to a new language... Even if you aren't particularly skilled in the shortcuts a given language/platform offers, it does help you understand a given algorithm.

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.

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.

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.

When I was doing numerical analysis and computational physics, this is also exactly what I did. Work out all the equations then port them straight into C or fortran.

And I was a comp sci major first and a physics major second. You spend over a decade doing math with single letter variables. Hard habit to break I guess.

Looks like it is implemented from this http://stackoverflow.com/a/18516731 answer, which itself is inspired from another source

Compression, encoding, encryption, etc. is more maths and computer science than "programming".

Of course it technically is programming don't get me wrong but it isn't "make a CRUD app with a simple UI" kind of programming.

Browse this snippet with hover overlays and semantic linking: https://code.woboq.org/lzfse/lzfse/src/lzvn_encode_base.c.ht...

It's code like this that has an exploit several years in the future given an edge case that is hard to fathom

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.

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.

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.

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.

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.

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.

That looks like a host of buffer overflow vulnerabilities waiting to happen.

I think I'll stick with zlib.

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.

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.

It looks like it was run through a Javascript minifier.

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

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?

What does return have to do with OO?

(If you want to be glib, complain about misplaced FP perhaps?)

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?

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.

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)

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.

Functions don't need to follow the ABI unless they're externally visible. If you use -fvisibility=hidden GCC will do whatever it wants for each function as it sees fit.

Interprocedural register allocation can work better than inlining too, because it keeps the code size smaller, and direct calls have almost no speed penalty.

Exported functions are entirely different than vast majority of the code, the exported ones do need call conventions, so they can be linked. But it's entirely not true that ONLY functions marked as 'inline' would be inlined. You can also direct GCC to try to integrate all “simple enough” functions into their callers with the option -finline-functions (includeded in -O3).[0]. O2 includes inline small functions [1]:

[0]: https://gcc.gnu.org/onlinedocs/gcc/Inline.html [1]: https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html

Are you sure? This does not match my experience. Rather, compilers inline stuff if they think it's a good idea, and treat the "inline" keyword more like a hint.

This is not true. Gcc will inline everything it damn well wants to. It will definitely inline any function that is smaller than a function call, like small C++ accessors, and any other small function available at compile time like trivial constructors and the like. The "inline" keyword mainly serves to avoid ODR violations, not to inform the optimizer.

They seem to like a style that has rather constrained use of `return' (but uses deliberate amounts of goto instead).

Not sure why.

I assume is "one return only per function" rule http://programmers.stackexchange.com/questions/118703/where-...

Not quite, there are multiple returns, still.

But might be something related, eg like they are talking about a state machine in the description somewhere, and give at most one return per state, or something like that?

It's more DRY.

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

Reply on news.ycombinator.com