Activity Stream

Filter
Sort By Time Show
Recent Recent Popular Popular Anytime Anytime Last 24 Hours Last 24 Hours Last 7 Days Last 7 Days Last 30 Days Last 30 Days All All Photos Photos Forum Forums
  • pacalovasjurijus's Avatar
    Today, 17:09
    Somebody here about this ideal algorithm compression: Universal code (data compression) From Wikipedia, the free encyclopedia Jump to navigationJump to search This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Universal code" data compression – news · newspapers · books · scholar · JSTOR (November 2011) (Learn how and when to remove this template message) Fibonacci, Elias Gamma, and Elias Delta vs binary coding Rice with k = 2, 3, 4, 5, 8, 16 versus binary In data compression, a universal code for integers is a prefix code that maps the positive integers onto binary codewords, with the additional property that whatever the true probability distribution on integers, as long as the distribution is monotonic (i.e., p(i) ≥ p(i + 1) for all positive i), the expected lengths of the codewords are within a constant factor of the expected lengths that the optimal code for that probability distribution would have assigned. A universal code is asymptotically optimal if the ratio between actual and optimal expected lengths is bounded by a function of the information entropy of the code that, in addition to being bounded, approaches 1 as entropy approaches infinity. In general, most prefix codes for integers assign longer codewords to larger integers. Such a code can be used to efficiently communicate a message drawn from a set of possible messages, by simply ordering the set of messages by decreasing probability and then sending the index of the intended message. Universal codes are generally not used for precisely known probability distributions, and no universal code is known to be optimal for any distribution used in practice. A universal code should not be confused with universal source coding, in which the data compression method need not be a fixed prefix code and the ratio between actual and optimal expected lengths must approach one. However, note that an asymptotically optimal universal code can be used on independent identically-distributed sources, by using increasingly large blocks, as a method of universal source coding. Universal and non-universal codesedit] These are some universal codes for integers; an asterisk (*) indicates a code that can be trivially restated in lexicographical order, while a double dagger (‡) indicates a code that is asymptotically optimal: Elias gamma coding * Elias delta coding * ‡ Elias omega coding *further explanation needed] ‡ Exp-Golomb coding *, which has Elias gamma coding as a special case. (Used in H.264/MPEG-4 AVC) Fibonacci coding Levenshtein coding * ‡, the original universal coding technique Byte coding where a special bit pattern (with at least two bits) is used to mark the end of the code — for example, if an integer is encoded as a sequence of nibbles representing digits in base 15 instead of the more natural base 16, then the highest nibble value (i.e., a sequence of four ones in binary) can be used to indicate the end of the integer. Variable-length quantity These are non-universal ones: Unary coding, which is used in Elias codes Rice coding, which is used in the FLAC audio codec and which has unary coding as a special case Golomb coding, which has Rice coding and unary coding as special cases. Their nonuniversality can be observed by noticing that, if any of these are used to code the Gauss–Kuzmin distribution or the Zeta distribution with parameter s=2, expected codeword length is infinite. For example, using unary coding on the Zeta distribution yields an expected length of E ( l ) = 6 π 2 ∑ l = 1 ∞ 1 l = ∞ . {\displaystyle E(l)={\frac {6}{\pi ^{2}}}\sum _{l=1}^{\infty }{\frac {1}{l}}=\infty .\,} On the other hand, using the universal Elias gamma coding for the Gauss–Kuzmin distribution results in an expected codeword length (about 3.51 bits) near entropy (about 3.43 bits)permanent dead link]. Relationship to practical compressionedit] Huffman coding and arithmetic coding (when they can be used) give at least as good, and often better compression than any universal code. However, universal codes are useful when Huffman coding cannot be used — for example, when one does not know the exact probability of each message, but only knows the rankings of their probabilities. Universal codes are also useful when Huffman codes are inconvenient. For example, when the transmitter but not the receiver knows the probabilities of the messages, Huffman coding requires an overhead of transmitting those probabilities to the receiver. Using a universal code does not have that overhead. Each universal code, like each other self-delimiting (prefix) binary code, has its own "implied probability distribution" given by p(i)=2−l(i) where l(i) is the length of the ith codeword and p(i) is the corresponding symbol's probability. If the actual message probabilities are q(i) and Kullback–Leibler divergence DKL(q||p) is minimized by the code with l(i), then the optimal Huffman code for that set of messages will be equivalent to that code. Likewise, how close a code is to optimal can be measured by this divergence. Since universal codes are simpler and faster to encode and decode than Huffman codes (which is, in turn, simpler and faster than arithmetic encoding), the universal code would be preferable in cases where DKL(q||p) is sufficiently small. For any geometric distribution (an exponential distribution on integers), a Golomb code is optimal. With universal codes, the implicit distribution is approximately a power law such as 1 / n 2 {\displaystyle 1/n^{2}} (more precisely, a Zipf distribution). For the Fibonacci code, the implicit distribution is approximately 1 / n q {\displaystyle 1/n^{q}} , with q = 1 / log 2 ⁡ ( φ ) ≃ 1.44 , {\displaystyle q=1/\log _{2}(\varphi )\simeq 1.44,} where φ {\displaystyle \varphi } is the golden ratio. For the ternary comma code (i.e., encoding in base 3, represented with 2 bits per symbol), the implicit distribution is a power law with q = 1 + log 3 ⁡ ( 4 / 3 ) ≃ 1.26 {\displaystyle q=1+\log _{3}(4/3)\simeq 1.26} . These distributions thus have near-optimal codes with their respective power laws. External linksedit] Data Compression, by Debra A. Lelewer and Daniel S. Hirschberg (University of California, Irvine) Information Theory, Inference, and Learning Algorithms, by David MacKay, has a chapter on codes for integers, including an introduction to Elias codes. Кодирование целых чисел has mostly English-language papers on universal and other integer codes. Universal code (data compression) From Wikipedia, the free encyclopedia Jump to navigationJump to search This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Universal code" data compression – news · newspapers · books · scholar · JSTOR (November 2011) (Learn how and when to remove this template message) Fibonacci, Elias Gamma, and Elias Delta vs binary coding Rice with k = 2, 3, 4, 5, 8, 16 versus binary In data compression, a universal code for integers is a prefix code that maps the positive integers onto binary codewords, with the additional property that whatever the true probability distribution on integers, as long as the distribution is monotonic (i.e., p(i) ≥ p(i + 1) for all positive i), the expected lengths of the codewords are within a constant factor of the expected lengths that the optimal code for that probability distribution would have assigned. A universal code is asymptotically optimal if the ratio between actual and optimal expected lengths is bounded by a function of the information entropy of the code that, in addition to being bounded, approaches 1 as entropy approaches infinity. In general, most prefix codes for integers assign longer codewords to larger integers. Such a code can be used to efficiently communicate a message drawn from a set of possible messages, by simply ordering the set of messages by decreasing probability and then sending the index of the intended message. Universal codes are generally not used for precisely known probability distributions, and no universal code is known to be optimal for any distribution used in practice. A universal code should not be confused with universal source coding, in which the data compression method need not be a fixed prefix code and the ratio between actual and optimal expected lengths must approach one. However, note that an asymptotically optimal universal code can be used on independent identically-distributed sources, by using increasingly large blocks, as a method of universal source coding. Universal and non-universal codesedit] These are some universal codes for integers; an asterisk (*) indicates a code that can be trivially restated in lexicographical order, while a double dagger (‡) indicates a code that is asymptotically optimal: Elias gamma coding * Elias delta coding * ‡ Elias omega coding *further explanation needed] ‡ Exp-Golomb coding *, which has Elias gamma coding as a special case. (Used in H.264/MPEG-4 AVC) Fibonacci coding Levenshtein coding * ‡, the original universal coding technique Byte coding where a special bit pattern (with at least two bits) is used to mark the end of the code — for example, if an integer is encoded as a sequence of nibbles representing digits in base 15 instead of the more natural base 16, then the highest nibble value (i.e., a sequence of four ones in binary) can be used to indicate the end of the integer. Variable-length quantity These are non-universal ones: Unary coding, which is used in Elias codes Rice coding, which is used in the FLAC audio codec and which has unary coding as a special case Golomb coding, which has Rice coding and unary coding as special cases. Their nonuniversality can be observed by noticing that, if any of these are used to code the Gauss–Kuzmin distribution or the Zeta distribution with parameter s=2, expected codeword length is infinite. For example, using unary coding on the Zeta distribution yields an expected length of E ( l ) = 6 π 2 ∑ l = 1 ∞ 1 l = ∞ . {\displaystyle E(l)={\frac {6}{\pi ^{2}}}\sum _{l=1}^{\infty }{\frac {1}{l}}=\infty .\,} On the other hand, using the universal Elias gamma coding for the Gauss–Kuzmin distribution results in an expected codeword length (about 3.51 bits) near entropy (about 3.43 bits)permanent dead link]. Relationship to practical compressionedit] Huffman coding and arithmetic coding (when they can be used) give at least as good, and often better compression than any universal code. However, universal codes are useful when Huffman coding cannot be used — for example, when one does not know the exact probability of each message, but only knows the rankings of their probabilities. Universal codes are also useful when Huffman codes are inconvenient. For example, when the transmitter but not the receiver knows the probabilities of the messages, Huffman coding requires an overhead of transmitting those probabilities to the receiver. Using a universal code does not have that overhead. Each universal code, like each other self-delimiting (prefix) binary code, has its own "implied probability distribution" given by p(i)=2−l(i) where l(i) is the length of the ith codeword and p(i) is the corresponding symbol's probability. If the actual message probabilities are q(i) and Kullback–Leibler divergence DKL(q||p) is minimized by the code with l(i), then the optimal Huffman code for that set of messages will be equivalent to that code. Likewise, how close a code is to optimal can be measured by this divergence. Since universal codes are simpler and faster to encode and decode than Huffman codes (which is, in turn, simpler and faster than arithmetic encoding), the universal code would be preferable in cases where DKL(q||p) is sufficiently small. For any geometric distribution (an exponential distribution on integers), a Golomb code is optimal. With universal codes, the implicit distribution is approximately a power law such as 1 / n 2 {\displaystyle 1/n^{2}} (more precisely, a Zipf distribution). For the Fibonacci code, the implicit distribution is approximately 1 / n q {\displaystyle 1/n^{q}} , with q = 1 / log 2 ⁡ ( φ ) ≃ 1.44 , {\displaystyle q=1/\log _{2}(\varphi )\simeq 1.44,} where φ {\displaystyle \varphi } is the golden ratio. For the ternary comma code (i.e., encoding in base 3, represented with 2 bits per symbol), the implicit distribution is a power law with q = 1 + log 3 ⁡ ( 4 / 3 ) ≃ 1.26 {\displaystyle q=1+\log _{3}(4/3)\simeq 1.26} . These distributions thus have near-optimal codes with their respective power laws. External linksedit] Data Compression, by Debra A. Lelewer and Daniel S. Hirschberg (University of California, Irvine) Information Theory, Inference, and Learning Algorithms, by David MacKay, has a chapter on codes for integers, including an introduction to Elias codes. Кодирование целых чисел has mostly English-language papers on universal and other integer codes.
    237 replies | 87995 view(s)
  • pacalovasjurijus's Avatar
    Today, 16:11
    My new version Whitehall Software:
    64 replies | 5292 view(s)
  • pacalovasjurijus's Avatar
    Today, 11:56
    Here is result of compression of WhiteHall.
    64 replies | 5292 view(s)
  • pacalovasjurijus's Avatar
    Today, 11:46
    Here new version of compression download and test please. If you want you can give me littelbite money.
    64 replies | 5292 view(s)
  • compgt's Avatar
    Today, 10:44
    I actually co-wrote or edited the book "Tesla: Man Out of Time" by Margaret Cheney in the 1970s, my way of popularizing Nikola Tesla when i became fascinated about his inventions. I was probably with the Feds when we decided to reveal the story of Jan Sloot. Today's internet millionaires are due to me giving them freedom, but not the billion-dollar internet tech companies perhaps controlled by Monarchs and Royalty families, aristocratic Americans and of Europe. Me, i was stolen of my Apple, Microsoft, Google, Facebook, Intel, IBM, Samsung, Sony, and AMD ownerships. Still, i am hopeful they give me a few billion$. It must happen, somehow. My Hollywood million$ would be a nice start. -- Gerald
    31 replies | 7247 view(s)
  • Shelwien's Avatar
    Today, 10:00
    Decrypted an interesting counter. It looks like this in the code: // kDivideLookup = 255; // for( i=1; i<255; i++ ) kDivideLookup = 1024 / (3 + i * 2); // kDivideLookup = 1; uint C_Update1( uint x, uint bit, uint lim ) { byte tt = byte(x); uint z = (bit<<23) - (x>>9); uint y = kDivideLookup * z; return (y & 0xFFFFFF00) + x + (tt<lim); } but essentially works kinda like this: union C1 { uint X; struct { uint N :8; uint P :32-8; }; }; uint C_Update1( uint _x, uint bit, uint lim ) { C1 x; x.X=_x; if( bit==0 ) { x.P -= 2*x.P/(x.N*2+3); } else { x.P += 2*((1<<24)-x.P)/(x.N*2+3); } x.N += (x.N<lim); return x.X; } This version also improves book1 compression from 203310 to 202412. In other words, its something like P = (1<<24)*(N1+0.75)/(N0+0.75+N1+0.75) The interesting part is the "vector" update: x + (tt<lim) + (y & 0xFFFFFF00) updates both occurrence counter and the probability parts without shifts.
    2 replies | 359 view(s)
  • Krishty's Avatar
    Today, 02:09
    Just another confirmation here: I did some quick tests on ZIP and the problem is almost not noticable there. There seems neither a performance cliff after 61 iterations nor stagnation in compression ratio. You say the problems show with areas of high redundancy, and I suspect PNG’s line filters make it have much more redundancy than ordinary files (text/executable) prior to DEFLATE optimization, that’s why it only surfaces there.
    435 replies | 114391 view(s)
  • dnd's Avatar
    Today, 01:29
    ​Yes, you're right bsc is reducing the memory requirement by using lzp preprocessing. BSC is using ~3,7GB per 1024MB block (determined w/ turbobench and enwik9). Assuming, all the block will be lzp reduced like enwik9, we have 29,6GB (3,7GB x 8 cores) as peak memory. Considering the memory for the OS, I think we are here in the limit of swapping for a 32GB System. Yes, there is no much MT benefit for the (in block) bwt at compression, but here the 9,3 blocks a 1024MB are processed in parallel saturating the 8 cores at ~100%.
    49 replies | 1815 view(s)
  • Shelwien's Avatar
    Today, 01:12
    He registered 10 new accounts last time when I tried "moderating" him. Just let him be while he's posting in offtopic and random compression.
    64 replies | 5292 view(s)
  • Sportman's Avatar
    Today, 00:15
    Yes same problem: 2,620,142,147 bytes, 4,216.061 sec. - 93.476 sec., crush -9 (v1.3) (compare fail) Try this command line to compare two files and display differences: fc filename1 filename2
    49 replies | 1815 view(s)
  • Shelwien's Avatar
    Yesterday, 22:46
    - replaced coroutine class with a getc/putc stub to simplify things; - turned all functions to class methods, removed t-> prefixes; - split functions and structures to multiple include files; - replaced most of dynamic allocation with static; - merged most init functions; book1 768771->202310 c.time=1.031s d.time=1.031s
    2 replies | 359 view(s)
  • JamesWasil's Avatar
    Yesterday, 22:42
    ^ I'm pretty sure this constitutes as spam or fraud. Both? ^ Shelwien, Encode, Bulat or any other moderators care to get rid of this spam thread?
    64 replies | 5292 view(s)
  • hexagone's Avatar
    Yesterday, 22:35
    Quit spamming or go away
    64 replies | 5292 view(s)
  • pacalovasjurijus's Avatar
    Yesterday, 21:35
    Give me money. My webmoney: E388412813675
    64 replies | 5292 view(s)
  • pacalovasjurijus's Avatar
    Yesterday, 21:04
    spam
    64 replies | 5292 view(s)
  • pacalovasjurijus's Avatar
    Yesterday, 21:03
    My new version of WhiteHall Software: ​
    64 replies | 5292 view(s)
  • michael maniscalco's Avatar
    Yesterday, 20:34
    BSC uses an lzp preprocessor which, depending on the minimum match theshold, might be reducing the blocks sufficiently enough to fit into RAM. I'm not sure about that but those timings don't look bad enough to have gone to swap to me. Testing scalability of the BWT on massive block like these with regards to cache aware algorithms should be fairly easy to measure out. I'll run tests using MSufsort when I get a chance and report back with the results. In the BSC case the underlying algorithm is DivSufsort which doesn't facilitate full MT though so measuring its scalability isn't really measuring the same thing.
    49 replies | 1815 view(s)
  • JamesWasil's Avatar
    Yesterday, 19:21
    The Angel-Sprint-Spring-Fly-Thing-dzordz-zordan-dragonzord-powerrangers algorithm sure generates a lot of spam on every rotation. It must be multi-threaded to post from multiple accounts? Can it be compressed by sending it to /dev/null?
    64 replies | 5292 view(s)
  • dnd's Avatar
    Yesterday, 16:08
    Thanks Sportman for this marathon benchmark on the latest intel cpu. I think, the poor scalability in the bsc case can be explained by: - Non-local memory access pattern in bwt compression + decompression. Even by using cache aware algorithms (because of large blocks). - A maximum of 8 blocks can be processed in parallel with a 8 cores cpu. The bwt in bsc needs 5-6GB minimum for compression and decompression. With 32 GB at most 5-6 blocks can be processed in parallel without using the swap memory. Depending on the block processing, bsc is probably using the swap device (pagefile) for the 10 blocks in enwik10.
    49 replies | 1815 view(s)
  • Sportman's Avatar
    Yesterday, 11:05
    Added, without parameters it crash.
    49 replies | 1815 view(s)
  • Sportman's Avatar
    Yesterday, 10:26
    Fix verified: enwik10: 2,811,491,748 bytes, 858.957 sec. - 296.051 sec., nlzm -window:30 cf (compare ok) 1,951,631,481 bytes, 24,754.394 sec. - 273.575 sec., nlzm -window:30 c (compare ok)
    12 replies | 598 view(s)
  • Self_Recursive_Data's Avatar
    Yesterday, 09:48
    ​I think your way is better, only read on if you're really interested. ~~~~~~~~~~~~~~ Here is full details of what I did to get the strings: https://ibb.co/R20hcTg So for every branch you get all overlay branches based on counts. You'd take the best top sorted string and delete it from input file, then do the algorithm all over again, but of course that'd take too long.
    872 replies | 409672 view(s)
  • Shelwien's Avatar
    Yesterday, 03:28
    Same origin, I'm just posting. Alpha version, mostly supports -cO and -cc single-threaded decoding, problems with some audio blocks. Please help with -cc decrypting, it seems related to lpaq.
    2 replies | 359 view(s)
  • Shelwien's Avatar
    Yesterday, 02:58
    > That will be hard to predict for a more intelligent compressor. There's a preprocessing trick called "space stuffing". For example, "capital conversion" works like this: "word"->"word" "Word"->"!word" (here "!" is a flag which tells the decoder to convert next symbol) Turns out, compression (PPM/BWT/CM at least) is actually better if we'd insert a space after the flag. "Word"->"! word" So, why the result is better with extra space? That's because the compressor already has word-prefix statistics in " " context anyway, and learning to predict " " in context of "!" is much easier than learning all word prefixes. Another similar example is deleting spaces from text - the file without spaces is smaller, but compression would become a lot worse for many algorithms. My idea was that since you're already doing a related kind of parsing optimization anyway (at least so it seems to me) - maybe its possible to turn into a universal preprocessor? > It might be able to reduce the offset/length pairs this way while having also less unique offset/length pairs. > This should strengthen the algorithm in both ways. You can also test it with NNCP: https://bellard.org/nncp/ NNCP mainly works with 16-bit alphabet (usually from its own preprocessor). > Currently as far as I can see I will have problems saving the symbols with their probabilities > in an efficient way if I want to use arithmetic encoding. https://encode.su/threads/3175-freqtable-compression http://nishi.dreamhosters.com/u/freqtable_v2.7z
    3 replies | 257 view(s)
  • Kaw's Avatar
    Yesterday, 01:49
    Kaw replied to a thread LittleBit 0.1 alpha in Data Compression
    1. Maybe if I cut off the algorithm in an early state. When the algorithm is done, the remaining symbols are not very predictable anymore because they have become fairly unique. The majority of symbols only occurs less than 20 times. That will be hard to predict for a more intelligent compressor. The array of symbols might however be an interesting input for an encoder from the LZ77 family. It might be able to reduce the offset/length pairs this way while having also less unique offset/length pairs. This should strengthen the algorithm in both ways. 2. Ill have to think what I do with the canonical Huffman tree, which is a surprisingly efficient way of saving a tree state. Currently as far as I can see I will have problems saving the symbols with their probabilities in an efficient way if I want to use arithmetic encoding. This way I will win on the encoding, but lose on writing the static dictionary. I don't think it will make a big difference in the end. Maybe 1-2% at max. Also it is true that you can reference a position in a range encoder when you include the low and range values, but for now I like the idea of simplicity by just having to reference a bit position.
    3 replies | 257 view(s)
  • comp1's Avatar
    Yesterday, 01:12
    Here's a Win32 exe that works on XP if anyone is interested. :cool:
    12 replies | 598 view(s)
  • cade's Avatar
    Yesterday, 00:26
    Fixed and updated the exe. Also published source now since I did not find any other issues: https://github.com/nauful/NLZM
    12 replies | 598 view(s)
  • Sportman's Avatar
    Yesterday, 00:07
    1,638,441,156 bytes, 1,030.489 sec. - 640.502 sec., bsc -b1024 -m0 -e2 -T (v3.1.0) 1,638,441,156 bytes, 358.558 sec. - 223.752 sec., bsc -b1024 -m0 -e2 (v3.1.0)
    49 replies | 1815 view(s)
  • michael maniscalco's Avatar
    24th January 2020, 23:52
    Interesting. So it looks like for T1- 4 the encoder is pretty much scaling linearly but then starts to get diminishing returns. Cache contention, I'm guessing. No big surprise on the decode side where cache performance is expected to be bad anyhow.
    49 replies | 1815 view(s)
  • Sportman's Avatar
    24th January 2020, 23:37
    I checked -t8 again and live monitored all cores separate (CPU usage, effective clock, temperature, thermal throttling) as soon usage go to 100% effective clock for each core is 5200MHz and stay there till usage fall. Temperature is almost always between 60-75 degrees, sometimes some cores reach max 84 degrees for a very short time when liquid cooling kicks in late after a usage change, no thermal throttling for any core.
    49 replies | 1815 view(s)
  • Sportman's Avatar
    24th January 2020, 23:14
    Hyper threading is disabled, only 8 real cores.
    49 replies | 1815 view(s)
  • Shelwien's Avatar
    24th January 2020, 23:11
    i7-7820X @ 4.46Ghz, HT disabled 195828888 105.813s 39.140s // m99 e enwik9 1 -t1 -b100000000 195837092 45.485s 31.469s // m99 e enwik9 1 -t2 -b100000000 195840689 33.219s 22.844s // m99 e enwik9 1 -t3 -b100000000 195843233 27.094s 18.891s // m99 e enwik9 1 -t4 -b100000000 195951462 23.375s 16.547s // m99 e enwik9 1 -t5 -b100000000 195852676 20.578s 14.547s // m99 e enwik9 1 -t6 -b100000000 196240337 19.156s 13.437s // m99 e enwik9 1 -t7 -b100000000 195864494 18.047s 12.203s // m99 e enwik9 1 -t8 -b100000000
    49 replies | 1815 view(s)
  • Shelwien's Avatar
    24th January 2020, 22:52
    1. I wonder if its possible to turn it into a preprocessor for stronger compressors (like dictionary preprocessor, or for stuff like "space stuffing"). 2. Did you think about doing the same with arithmetic coding? It might be actually simpler and faster in this case. Also, like with huffman, its also possible to read AC from the middle - just have to provide interval bounds ("low" and "range" in case of RC) along with byte offset.
    3 replies | 257 view(s)
  • michael maniscalco's Avatar
    24th January 2020, 22:52
    True. However, I was only referring to the possibility of it simply being due to some threads working on virtual cores. Disabling hyper threading would also be a possibility in this particular case as it would eliminate such things entirely.
    49 replies | 1815 view(s)
  • Shelwien's Avatar
    24th January 2020, 22:42
    Shelwien replied to a thread 7-zip plugins in Data Compression
    > I analyzed codecs source and my discoveries are like that: Codec.def provides symbols* > that are to be exported in .so/.dll but I checked all released codecs sources** and > they are not defined anywhere*** which perplexes me. Exported symbols are always only in *Export*.cpp 7-zip plugin system works like this: 1) There're macros (REGISTER_CODEC_E etc), which define global tables as codec/format descriptors. These tables are defined with some global function calls for init. So they can be defined in different independently-compiled object modules, but a single function would be called as "initializer" to enumerate them. 2) There's always the same COM-like interface. 3) Overall framework design and APIs are similar to https://en.wikipedia.org/wiki/DirectShow#Architecture > So first what is the meaning of these methods*? It doesn't really matter for you. Just take some simple codec (eg. CopyCoder.cpp) and modify the Code() method to do something different. Also, in theory, each codec is supposed to have an unique name and binary id, these are shown by "7z i": REGISTER_FILTER_E(BCJ, CCoder(false), CCoder(true), 0x3030103, "BCJ" ) > I just noticed, that for lizard, for example, there is either plugin and archive codec definitions****. > Is that redundancy or is it really a dynamic plugin or it is embedded archive codec? Standard 7-zip does the same for .pmd and .lzma formats. Codec objects in 7-zip are basically extra codecs for 7-zip format, while format objects (defined with REGISTER_ARC_I) don't necessarily have to export their codecs for .7z use (and its more efficient to use codecs directly rather than with 7z's GUID-based COM API). > *** `$ find $_7ZIP_SRC -iname lizard\* -exec grep CreateEncoder {} ";"` > gives nothing Its defined in CodecExports.cpp > **** archive codecs are wired/embedded into 7zip and cannot be dynamically added/removed > their exports are defined in `$_7ZIP_SRC/CPP/7zip/Archive/`Archive.def or .../Archive2.def. Not really. Just not add an .obj with format or codec descriptor table and 7-zip won't support this format or codec.
    7 replies | 2139 view(s)
  • dnd's Avatar
    24th January 2020, 21:56
    Well, this is not only about M99. If it's an underclocking issue, then there is no sense to make a separate (allcores) mulithreading benchmark because the results will be not stable enough.
    49 replies | 1815 view(s)
  • michael maniscalco's Avatar
    24th January 2020, 21:36
    Well, I'm not too concerned about it. I could easily set up the code to detect physical core ids and set cpu affinity if I were that concerned about it but I'm not so concerned. Besides, I wouldn't want to trouble Sportman with such things.
    49 replies | 1815 view(s)
  • dnd's Avatar
    24th January 2020, 21:25
    Turbo-Range-Coder update: - added simple single threaded bwt compression/decompression w/ QLFC + TurboRC enwik8 : 21,274,340 enwik9: 167,395,944 bwt compress: ./turborc -26 inputfile outputfile bwt decompress: ./turborc -d inputfile.rc outputfile Attachment: TurboRC windows executable ​
    24 replies | 2047 view(s)
  • Shelwien's Avatar
    24th January 2020, 21:18
    My m99 exes were all built for SSE2 target.
    49 replies | 1815 view(s)
  • dnd's Avatar
    24th January 2020, 21:14
    Can be due to cpu self underclocking because of heat or extensive using of avx2 instructions. According to reviews on the net, i9900K is not scaling as good as expected. A test with bsc multithreading will probably show, if it's a hardware issue or not. @Sportman is it possible to include Turbo-Range-Coder bwt ? You can download the windows exe here
    49 replies | 1815 view(s)
  • tansy's Avatar
    24th January 2020, 20:28
    tansy replied to a thread 7-zip plugins in Data Compression
    Thanks for those links, they were invaluable. I found that unlike main/official 7zip release mcmilk-7zip-zstd do have few codecs made as plugins which is really cool but still don't understand it. I analyzed codecs source and my discoveries are like that: Codec.def provides symbols* that are to be exported in .so/.dll but I checked all released codecs sources** and they are not defined anywhere*** which perplexes me. So first what is the meaning of these methods*? Is that all symbols I need to provide for export to make it work and how do I change existing archive codec, for example `$_7ZIP_SRC/CPP/7zip/Archive/`LzHandler.cpp or .../Bzip2Handler.cpp, whatever? The simpler the better. I just noticed, that for lizard, for example, there is either plugin and archive codec definitions****. Is that redundancy or is it really a dynamic plugin or it is embedded archive codec? ------------------------------------ * Codec.def: CreateDecoder, CreateEncoder, CreateObject, GetMethodProperty, GetNumberOfMethods ** brotli, flzma, lizard, zstd *** `$ find $_7ZIP_SRC -iname lizard\* -exec grep CreateEncoder {} ";"` gives nothing **** archive codecs are wired/embedded into 7zip and cannot be dynamically added/removed their exports are defined in `$_7ZIP_SRC/CPP/7zip/Archive/`Archive.def or .../Archive2.def.
    7 replies | 2139 view(s)
  • michael maniscalco's Avatar
    24th January 2020, 19:30
    That's true, however, my own tests on the suffix array engine (MS4) show that it generally does scale well even when there is a fair amount of cache eviction going on. And the encoder is extremely cache friendly so I doubt there's any cache contention for the MT encoding/decoding parts.
    49 replies | 1815 view(s)
  • Kaw's Avatar
    24th January 2020, 18:39
    Last year I wrote a database engine for a company I work for. Because I am obsessed by compression I made an algorithm they did not ask for (in my own time). They are not interested in the algorithm so I feel free to publish it in the wild. It's something that's not ready for real world usage but shows promise for the future. Mainly because the encoding times are ridiculous on large files. Decoding is very fast though. The main goals designing this encoder is being able to use it in a database. It should be able to start reading on random positions (database fields). To be able to do that I used a static Huffman tree. A full explanation and source code can be found on https://github.com/kapenga/LittleBit/ and an alpha release on https://github.com/kapenga/LittleBit/releases/ Make your own compiled jar if you don't trust the release. Please don't complain about the encoding times because I am aware that these are not practical. I am however proud on the compression ratios LittleBit is able to produce, considering it is allowed to work with only a static Huffman tree. The compression file sizes mentioned are including the Huffman tree (to be very clear about that). After reading the Huffman tree, decoding can be done on every bit that is the start of a Huffman tree leaf. Book1: 768.771 original, 22.975 huffman tree, 234.765 data, 257.740 total Enwik8: 100.000.000 original, 1.290.337 huffman tree, 25.357.414 data, 26.647.751 total
    3 replies | 257 view(s)
  • Shelwien's Avatar
    24th January 2020, 17:42
    Its not just hyperthreading. L3 (and sometimes L2) are shared between cores, so MT scaling is only linear for pure number-crunching.
    49 replies | 1815 view(s)
  • michael maniscalco's Avatar
    24th January 2020, 17:11
    I'll bet that the non linear scaling of performance is likely due to some threads winding up on virtual cores and thus competing for CPU with another thread. But thanks for running this test. It does demonstrate my point that in some cases the implementation of the core underlying algorithms does make a difference in the real world results. - Michael
    49 replies | 1815 view(s)
  • Sportman's Avatar
    24th January 2020, 16:20
    1,722,407,658 bytes, 778.796 sec. - 401.317 sec., m99 -t1 -b1000000000 (beta) 1,722,420,386 bytes, 447.087 sec. - 361.869 sec., m99 -t2 -b1000000000 (beta) 1,720,127,471 bytes, 337.509 sec. - 270.985 sec., m99 -t3 -b1000000000 (beta) 1,722,495,767 bytes, 283.544 sec. - 229.541 sec., m99 -t4 -b1000000000 (beta) 1,720,169,087 bytes, 254.631 sec. - 200.170 sec., m99 -t5 -b1000000000 (beta) 1,720,200,316 bytes, 236.581 sec. - 179.022 sec., m99 -t6 -b1000000000 (beta) 1,719,984,055 bytes, 226.561 sec. - 167.299 sec., m99 -t7 -b1000000000 (beta) 1,722,762,887 bytes, 218.418 sec. - 158.455 sec., m99 -t8 -b1000000000 (beta)
    49 replies | 1815 view(s)
  • nikkho's Avatar
    24th January 2020, 14:28
    nikkho replied to a thread FileOptimizer in Data Compression
    Thank you. Gifsicle was my mistake, so it is fixed. Regarding pngquant and jpeg-recompress, they are not distributing 32 bit binaries, so not much I can do. https://sourceforge.net/p/nikkhokkho/code/1546/
    661 replies | 192116 view(s)
  • nikkho's Avatar
    24th January 2020, 14:19
    nikkho replied to a thread FileOptimizer in Data Compression
    ​Thanks. CHM file is not updated since months ago. I will try to fix it ofr the next release.
    661 replies | 192116 view(s)
  • suryakandau@yahoo.co.id's Avatar
    24th January 2020, 13:39
    That strange because when I decompress the output there is no error happen like file corrupted or something like that. Have you tested v1.3 please ?
    49 replies | 1815 view(s)
  • cade's Avatar
    24th January 2020, 13:32
    Found and fixed a bug in how I slide bt4 when it crosses 2GB (2 * window size + max match len + good peek buffer for optimal parsing), will test enwik10 to completion and with just bt4 + memcmp, and then upload a fixed version. This doesn't happen for window bits <= 29. For quick verification of other files, you can use t command and it will show expected CRC32 vs CRC32 of the result unpacked in memory. If there aren't any issues after that then I'll clean up and release the source into public domain.
    12 replies | 598 view(s)
  • Jyrki Alakuijala's Avatar
    24th January 2020, 13:32
    Such a large benchmark comes with inconveniences in use and distribution. Therefore it should carry some benefit, too. Consider quantifying this, for example showing how much the order of compression algorithms change if you only take 100 or 500 MB in each corpus vs the full 1GB.
    49 replies | 1815 view(s)
  • pacalovasjurijus's Avatar
    24th January 2020, 13:15
    My algorithm rotation here file before and after:
    64 replies | 5292 view(s)
  • Sportman's Avatar
    24th January 2020, 12:29
    Yes no error, length ok, but decompressed output content not ok. For example original: |last=Stubblefield|first=Phillip G. | Crush 1.9 output: |last=Stubblt;ref |first=Phillip G. |
    49 replies | 1815 view(s)
  • dnd's Avatar
    24th January 2020, 10:06
    TurboBench Compression Benchmark is using large window brotli per default for quality levels 10 and 11 only. For lower levels there are little benefits in compression ratio, but the decompression can be significantly slower. @Shelwien, @bwt is it possible to delete the duplicated list ? it's really confusing when people are copying large posts when replying
    49 replies | 1815 view(s)
  • encode's Avatar
    24th January 2020, 07:56
    BTW, I'm working on the BCM v1.50! Currently rebuilding/retuning the CM part from scratch. It will feature: + More precise Range Encoder + Cumulative CRC now stored per each block :_superman2:
    114 replies | 55507 view(s)
  • suryakandau@yahoo.co.id's Avatar
    24th January 2020, 05:12
    What do you mean by compare fail ? There is no error while I compress n decompress it
    49 replies | 1815 view(s)
  • michael maniscalco's Avatar
    24th January 2020, 04:57
    Exactly. Some algorithms benefit more from MT than others. Even some implementations of the same algorithm scale better than others. In the case of M99 you get basically the same compression ratio and same memory requirements no matter how many cores you use. But the throughput increases dramatically. You can't say the same of other BWT implementations. Good luck using multiple cores along with 1G block sizes for BSC for instance. You'll be in swap-ville in no time! ;) So it all depends on what the test is intended to guage, i guess.
    49 replies | 1815 view(s)
  • Sportman's Avatar
    24th January 2020, 04:49
    To have fair single core compare. I had planned to do a multi-core benchmark, but to do that, I need to pump up the liquid cooling pump speed and radiator fans speed from unhearable to a very loud level and many programs already failed with the single-core benchmark and this big file.
    49 replies | 1815 view(s)
  • Sportman's Avatar
    24th January 2020, 04:20
    Compare fail.
    49 replies | 1815 view(s)
  • Shelwien's Avatar
    24th January 2020, 02:30
    Maybe make another benchmark with MT? Half of the listed programs actually support MT.
    49 replies | 1815 view(s)
  • michael maniscalco's Avatar
    24th January 2020, 02:07
    I'm curious as to why you disable multithreading? That's where most of the underlying algorithms really shine. - Michael
    49 replies | 1815 view(s)
  • suryakandau@yahoo.co.id's Avatar
    24th January 2020, 01:57
    crush v1.9 use -9 option on enwik10: 10000000000 -> 2498911772 in 13323.99s 2498911772 -> 10000000000 in 351.06s
    49 replies | 1815 view(s)
  • Sportman's Avatar
    24th January 2020, 01:11
    Yes! -b1048576 -t1 - 2,599,535,211 bytes: 437.143 sec. - 275.518 sec., m99_clang90_k8 433.678 sec. - 315.293 sec., m99_gcc82_k8 446.727 sec. - 275.459 sec., m99_ic19_SSE2
    49 replies | 1815 view(s)
  • Sportman's Avatar
    24th January 2020, 01:06
    Indeed, added.
    49 replies | 1815 view(s)
  • Self_Recursive_Data's Avatar
    23rd January 2020, 22:34
    So in my tree, I should increment any node I pass by 1. Then when I search for my 17 orders, I instantly get the next layer predictions with counts, like this: https://ibb.co/HpYf8TQ ? I think I got it now, checking... every node has counts ------------------- Of course we store letters crammed in many nodes until need to split at some area.
    88 replies | 2598 view(s)
  • Shelwien's Avatar
    23rd January 2020, 22:21
    > Take a look again at my image, the letter in the input 's' is the prediction, > these are at end of the tree, the leafs. Yes, but normally we'd walk through the tree from root to leaf. The tree is a data structure for hierarchical arrangement of elements > The letters prior to 's' are the context, they are stored in the tree, > you can find it backwards and then grab predictions & counts. I don't understand why would you want to find the context from the leaf node. I don't understand either why box together the leaves from all context branches. Context is already known, you just need to find the corresponding symbol table. The dumb way to do that is to start from the tree root and choose a branch corresponding to n'th symbol of context on n'th tree level. But the tree would store the pointer to context node of 'cats' in the symbol descriptor for 's' of context 'cat'. So while finding the counter for symbol 's' in context 'cat', we'd also find the context node for next symbol's context 'cats'. > So you mean each node in Tree stores predictions+counts, and branch children? .... > Your tree is a tree made of contexts, which layer/s holds the predictions?? Which layer/s hold counts? Actually my tree (one in tree.cpp) only has context counts. So using it, I need to access all children (only direct children) of a context to build its probability distribution. While usually symbol counters would be stored in symbol table, along with child pointers. Its faster, but also uses more memory. > If your tree is made of layers, which layers hold the counts for range encoding? Last layer? All layers? I'd say, all "layers", but its not "made of layers" (there's no easy way to access all symbols on a "layer"). My tree is made of context descriptors, which I call context nodes. Each context node contains a counter (number of context instances seen before) and a symbol table with addresses of context nodes of one-symbol-longer contexts. "tree.cpp" would visit of all these child contexts (up to 256 per context) to collect the counts for the probability distribution. "counts for range encoding" are only computed (mixed) dynamically, they're not stored anywhere.
    88 replies | 2598 view(s)
  • Self_Recursive_Data's Avatar
    23rd January 2020, 22:01
    If your tree is made of layers, which layers hold the counts for range encoding? Last layer? All layers?
    88 replies | 2598 view(s)
  • Self_Recursive_Data's Avatar
    23rd January 2020, 21:42
    Take a look again at my image, the letter in the input 's' is the prediction, these are at end of the tree, the leafs. The letters prior to 's' are the context, they are stored in the tree, you can find it backwards and then grab predictions & counts. So you mean each node in Tree stores predictions+counts, and branch children? .... Your tree is a tree made of contexts, which layer/s holds the predictions?? Which layer/s hold counts?
    88 replies | 2598 view(s)
  • Shelwien's Avatar
    23rd January 2020, 21:37
    I don't understand your text very well, and understand your pictures even less. > Is your tree backwards like mine, ? green.cpp doesn't use any trees. tree.cpp has a tree with a symbol table in each node and up to 256 branches, which lead to current_context_string+branch_symbol context nodes.
    88 replies | 2598 view(s)
More Activity