MS-PACK glitch

Hello Dmitry! Fri Jun 20 1997, Dmitry Lomov (812/08.14) concocted a letter to All: DL> I just came across a glitch in all my favorite DL> by MS-PACK. I came across a block that Yes, apparently the glitch is in the program. and most likely - from incomplete understanding of the packaging algorithm by the author or his successor (after all, I I’m inclined to think that SME is a modified trash) DL> Some other DL> other packers: DSQ 4.12 (by RUSH), DL> CC3.11 (by KSA), EC (by ESV). I’ve never seen these, sorry for the greyness. ;( and you haven’t tried good old Sendetskogo? or the same trash? DL> I'll tell you how to deal with the glitch, but sleep- DL> I'll try to imagine what I am- DL> is the cause. I'll try to separate the flies from the cutlets and tell you how to deal with the glitch _correctly_ fight DL> As you know, MS-PACK does not require additional DL> memory outside the addresses of the block that - DL> is obtained as a result of unpacking DL> excluding 193 bytes where the depacker sits. Well, firstly, there should be 243 “free” bytes at the beginning of the block (actually notquite at the beginning, but that’s not the point) further, your reasoning is quite correct (I’ll leave it purely for clarity) DL> Unpacking is carried out to the same addresses where DL> the packed block is sitting, while unpacking DL> is carried out from low to high addresses DL> and at the beginning of the process the picture is like this: DL> The address increases there... DL> -+-+--+--+--+--+--+--+--+--+-> DL> [-+--- Initial unpacked block -+--] DL> [-{depacker}{packed block}-] DL> blocks are transferred: DL> depacker is placed in a 193 byte buffer DL> to any (specified) address DL> and the packed block is placed under the ceiling DL> memory used, i.e. under the ceiling DL> of the block to be unpacked. DL> [-+--- Initial unpacked block -+--] DL> [--packed block--] DL> ^ ^ DL> A<<<<<<<<<<<<<<<< DL> Unpacking is carried out from point B to point A, DL> in this case the points are moved through memory DL> up, and by the end of the process they match. DL> Assumes nowhere in the middle DL> process A will not catch up with B, otherwise they will DL> data that has not yet been unpacked is corrupted. DL> A reserve has been made in the depacker for this purpose, and DL> last five bytes are sent from DL> reserve areas 193 bytes. DL> So, when I got a glitch, I preferred DL> put it somewhere closer to the end of the block DL> points overlapped. DL> I changed the depacker so that it appeared DL> additional gap between points. DL> [-+- Original unpacked block -+-] DL> [--packed block--] DL> ^^^^ DL> ends do not match DL> Unfortunately, this method is not always acceptable DL> yes, it is necessary that the field of the unpacked block DL> there was free space that can be used. DL> (ROM is not suitable for this purpose!!! ;)yes, and it is incorrect in the general case. you didn't understand the main thing - how everything should work in theory. try to comprehend the following thesis: if A has caught up with B, then for further parts packaging is ineffective. and now how to fight (I will leave most of the statements without evidence, from own laziness and in order to allow readers to enjoy not only contemplation, but also from a minimal thought process ;): Let's try to divide the original block into two parts: [packable head][non-packable tail] the criterion is clear as day and night - this is the difference in size between unpacked and packaged. Moreover, for head A will not catch up with B. Now let's see what we have from the goose: [source block] [head][tail] and here it is noticeable that the tail is already “sitting” in its own addresses, and the unpacker only needs to do the required work with his head; front view the beginning of the process: [ ] [packed head][tail] the last code of the algorithm will be the ending code, the penultimate code will be the chain code (not character - according to the condition of choosing the tail boundary). that it is enough to have “in reserve” It’s also clear - there’s a place for this same ending code; five bytes is even a lot - it seems In any case, three would be enough. where the error is in the absence or incorrect division of the block into two parts; I'm definitely too lazy to disassemble and look.By the way, the ideal theoretical limiting case when the block is not packed is the head is only from the ending code. probably 5 bytes are left for it (two more for the mined at the beginning of de). in this case, and the size closest to it the downloaded part is larger than the original one and the image after downloading (if the initial the address is the same) will be like this: [depacker][ block of packed data ] // what was downloaded [ ] // and this is the area of the source block It is obvious that there is no point in such “compression”, unless remove the depacker, then you can still win something. as a summary - what is the difference between a “hacker” and a programmer? ;) With best wishes, Michael.

Hello, Mikhail! MK> I'll try to separate the flies from the cutlets MK> and tell us how to do it _correctly_ MK> fight the glitch I really like your method of separation. curled up! Separated, but no specifics. To implement your method you need to re- dig a lot of code, and I, like you lazy... Although the method is very correct. I suggested a cheap and cheerful way. By the way, I would like to have a structure ZXZIP file and description of the algorithm, the thing is that he always packs better than the mentioned packers, and speed is not needed everywhere. Maybe I'll get around to writing CRUNCHER based on the ZXZIP algorithm. I would appreciate it if you would send them to me in any way convenient for you. MK> as a summary - what is the difference MK> "hacker" from a programmer? ;) That the hacker will launch STS, twirl and twirl and do something, so that everything works. The programmer will analyze for a long time, spew out terms, spit out calculations, gives birth to a mathematical model, it turns out a coherent theory, and, if by that time he will have time left, _maybe_, will write/rewrite software. Well, it may very well be... MK> With best wishes, Michael. Bye! And I'm waiting for an answer... -=LD=-

Hello Dmitry! Wed Jul 02 1997, Dmitry Lomov (812/08.14) concocted a letter to Michael Kondratyev: MK>> I'll try to separate the flies from the cutlets MK>> and tell us how to _correctly_ MK>> fight the glitch DL> I really like your method of separation DL> curled! Separated, but no specifics. You flatter me, this is not my way. in the same Sendets it has been used for a long time and successfully. DL> To implement your method you need to re- DL> dig a lot of code, and I, like DL> you lazy... about quite a lot - you are exaggerating, the working part of mspack is a small piece executed on the screen. although rewriting it... (this sink so old - it’s easier to buy a new one (c)). In addition, it would be nice to slightly modernize the search algorithm for the case a lot of nesting (well, it slows down a lot and only because it does this stupid search). You can also use full tables if available additional memory (for computers 256 and higher). I’ll probably even suggest an algorithm for determining the location of the end of the package without unnecessary passages (I just “made it up” - I don’t pretend to be absolutely correct): - a very general view of the packer can be represented as follows: loop until end of datalooking for a line not found: display byte code found: display the line code - enter a variable (hereinafter called saved) size - at least 3 bytes, signed, initial value 0; the ultimate goal will be to find the minimum for it - after each issuance of the byte/line code saved is modified: increased by the number of bits of the output code and is reduced by the number of bits “eaten” by this code. as is easy to see, for each single byte this is ultimately +1, for string-string modifier negative - a check for the minimum must be carried out _before_ each code issuance single character and after the end of the entire cycle. at the same time the current one is preserved state of the algorithm for min_saved - after the end of the entire packaging cycle, if min_saved==0 - everything goes to waste - data is not packed - otherwise the saved state is restored and the end of the algorithm code is issued. The "remaining" raw data goes to the tail. DL> Although the method is very correct. still not true, however. DL> I suggested a cheap and cheerful way. yes, and theoretically requiring a reserve of up to 1/8 of the original length. DL> By the way, I would like to have a structure DL> ZXZIP file and description of the algorithm structure - please: =========== Cut and save ===========ZxZip archive file header structure ╔══════╤═══════════════╤══════════ ══════════════════════════════════╗ ║Offset│ Field │ Description ║ ╟──────┼───────────────┼────────── ──────────────────────────────────╢ ║ +00 │ filename │ ║ ║ +08 │ extension │ ║ ║ +09 │ start address │ Just a copy of 14 bytes of a hard file ║ ║ │ /basic length │ header ║ ║ +0B │ length │ ║ ║ +0D │ sect.length │ ║ ╟──────┼───────────────┼────────── ──────────────────────────────────╢ ║ +0E │ packed size │ Packed file size ║ ╟──────┼───────────────┼────────── ──────────────────────────────────╢ ║ +10 │ CRC-32 value │ Polynomial checksum value ║ ╟──────┼───────────────┼────────── ──────────────────────────────────╢ ║ +14 │ pack method │ Packing method: ║ ║ │ │ 0 - Stored 1 - LZPress ║ ║ │ │ 2 - Shrunk 3 - Implode ║ ╟──────┼───────────────┼────────── ──────────────────────────────────╢ ║ +15 │ flags │ Miscellaneous ;-) ║║ │ │ bit0 - binary/text bit1..7 - reserved ║ ╚══════╧═══════════════╧══════════ ══════════════════════════════════╝ The initial file length is determined using the following algorithm: 1) Estimated length (for BASIC: w[+09]+4, for others: w[+0B]), if it exactly matches the length in sectors specified in b[+0D]; 2) Value b[+0D]*256 if there is no match. The archive is built from sequential parts, consisting of a header and a compressed data block of length w[+0E]. =========== Cut and save =========== DL> the thing is that he is always DL> packs better than the mentioned packers DL> and performance is not needed everywhere. DL> Perhaps I’ll get around to writing DL> CRUNCHER based on the ZXZIP algorithm. this is hardly worth doing - lzw requires quite a lot of additional memory, and implode makes abundant use of Huffman coding - for fast Unpacking requires somewhere around ~1.5k memory for tables (there are 2..3 of them). in general terms The algorithm is below (this is from infozip sources): =========== Cut and save =========== Explode imploded (PKZIP method 6 compressed) data. This compression method searches for as much of the current string of bytes (up to a length of ~320) in the previous 4K or 8K bytes. If it doesn't find any matches (of at least length 2 or 3), it codes the next byte. Otherwise, it codes the length of the matched string and its distance backwards from the current position. Single bytes ("literals") are preceded by a one (a single bit) and are either uncoded (the eight bits go directly into the compressed stream for a total of nine bits) or Huffman coded with a supplied literal code tree. If literals are coded, then the minimum match length is three, otherwise it is two. There are therefore four kinds of imploded streams: 8K search with coded literals (min match = 3), 4K search with coded literals (min match = 3), 8K with uncoded literals (min match = 2), and 4K with uncoded literals (min match = 2). The kind of stream is identified in two bits of a general purpose bit flag that is outside of the compressed stream. Distance-length pairs are always coded. Distance-length pairs for matched strings are preceded by a zero bit (to distinguish them from literals) and are always coded. The distance comes first and is either the low six (4K) or low seven (8K) bits of the distance (uncoded), followed by the high six bits of the distance coded. Then the length is six bits coded (0..63 + min match length), and if the maximum such length is coded, then it's followed by another eight bits (uncoded) to be added to the coded length. This gives a match length range of 2..320 or 3..321 bytes. The literal, length, and distance codes are all represented in a slightly compressed form themselves. What is sent are the lengths of the codes for each value, which is sufficient to construct the codes. Each byte of the code representation is the code length (the low four bits representing 1..16), and the number of values sequentially with that length (the high four bits also representing 1..16). There are 256 literal code values (if literals are coded), 64 length code values, and 64 distance code values, in that order at the beginning of the compressed stream. Each set of code values is preceded (redundantly) with a byte indicating how many bytes are in the code description that follows, in the range 1..256. =========== Вырежь и сохрани =========== MK>> как pезюме - в чем же отличие MK>> "хакеpа" от пpогpаммиста? ;) DL> В том, что хакер запустит STS, DL> повертит-покрутит, да и сделает что-нибудь, DL> дабы все работало. DL> Программист же будет долго анализировать, DL> изрыгать термины, плеваться выкладками, DL> gives birth to a mathematical model, exits DL> a coherent theory, and if by that time DL> he will have time left, _maybe_ DL> will write/rewrite the software. DL> Well, it may very well be... You didn’t understand anything (or didn’t want to). "hacker" will do anything to worked, but it may very well happen that he will not fully understand why According to the principles, it works (as it should work). but to understand this in general The cost of the work is commensurate with writing. and you just have to hope that he at least it won't make things worse. and if the process occurs sequentially through several "craftsmen", then the devil knows what might happen. approximately how to translate text from from the first language to the second, from the second to the third, from the third to the fourth, from on the fourth again to the first - it’s good if at least the meaning remains.. With best wishes, Michael.