6 ms·
Excerpt from the link : if (D == D_prev) { if (L == 0) { *q++ = 0xF0 + (x + 3); // XM! } else { *q++ = (L << 6) + (x
by 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 agoBlows 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 agoThat 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 agoSeems 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 agoWhen 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 agoIn 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 agoLooks like it is implemented from this http://stackoverflow.com/a/18516731 http://stackoverflow.com/a/18516731 answer, which itself is inspired from another source
- 2muchcoffeeman 10y agoWhen 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.
- satysin 10y agoCompression, 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.
- ec109685 10y agoIt's code like this that has an exploit several years in the future given an edge case that is hard to fathom
- addicted 10y agoThe 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 agoI'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 agoWhen 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 agoArithmetic 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 agoOr 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 agoI 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 agoBrowse 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 agoI 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 agoEh. 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 agoYeah 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 agoIn 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 agoThere 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 agoThat looks like a host of buffer overflow vulnerabilities waiting to happen. I think I'll stick with zlib.