Overview
| SHA1 Hash: | 59ad045fef5234bfca9e0a83eb1ab98d8214b981 |
|---|---|
| Date: | 2007-08-27 04:35:10 |
| User: | aku |
| Comment: | Completed the description of the delta encoder |
| Timelines: | ancestors | descendants | both | trunk |
| Other Links: | files | ZIP archive | manifest |
Tags And Properties
- branch=trunk inherited from [a28c83647d]
- sym-trunk inherited from [a28c83647d]
Changes
[hide diffs]Added art/encode10.dia version [5957690e4d]
@@ -1,1 +1,657 @@ - +<?xml version="1.0" encoding="UTF-8"?> +<dia:diagram xmlns:dia="http://www.lysator.liu.se/~alla/dia/"> + <dia:diagramdata> + <dia:attribute name="background"> + <dia:color val="#ffffff"/> + </dia:attribute> + <dia:attribute name="pagebreak"> + <dia:color val="#000099"/> + </dia:attribute> + <dia:attribute name="paper"> + <dia:composite type="paper"> + <dia:attribute name="name"> + <dia:string>#Letter#</dia:string> + </dia:attribute> + <dia:attribute name="tmargin"> + <dia:real val="2.5399999618530273"/> + </dia:attribute> + <dia:attribute name="bmargin"> + <dia:real val="2.5399999618530273"/> + </dia:attribute> + <dia:attribute name="lmargin"> + <dia:real val="2.5399999618530273"/> + </dia:attribute> + <dia:attribute name="rmargin"> + <dia:real val="2.5399999618530273"/> + </dia:attribute> + <dia:attribute name="is_portrait"> + <dia:boolean val="true"/> + </dia:attribute> + <dia:attribute name="scaling"> + <dia:real val="1"/> + </dia:attribute> + <dia:attribute name="fitto"> + <dia:boolean val="false"/> + </dia:attribute> + </dia:composite> + </dia:attribute> + <dia:attribute name="grid"> + <dia:composite type="grid"> + <dia:attribute name="width_x"> + <dia:real val="1"/> + </dia:attribute> + <dia:attribute name="width_y"> + <dia:real val="1"/> + </dia:attribute> + <dia:attribute name="visible_x"> + <dia:int val="1"/> + </dia:attribute> + <dia:attribute name="visible_y"> + <dia:int val="1"/> + </dia:attribute> + <dia:composite type="color"/> + </dia:composite> + </dia:attribute> + <dia:attribute name="color"> + <dia:color val="#d8e5e5"/> + </dia:attribute> + <dia:attribute name="guides"> + <dia:composite type="guides"> + <dia:attribute name="hguides"/> + <dia:attribute name="vguides"/> + </dia:composite> + </dia:attribute> + </dia:diagramdata> + <dia:layer name="Background" visible="true"> + <dia:group> + <dia:group> + <dia:object type="Standard - Box" version="0" id="O0"> + <dia:attribute name="obj_pos"> + <dia:point val="6,2"/> + </dia:attribute> + <dia:attribute name="obj_bb"> + <dia:rectangle val="5.975,1.975;12.025,22.025"/> + </dia:attribute> + <dia:attribute name="elem_corner"> + <dia:point val="6,2"/> + </dia:attribute> + <dia:attribute name="elem_width"> + <dia:real val="6"/> + </dia:attribute> + <dia:attribute name="elem_height"> + <dia:real val="20"/> + </dia:attribute> + <dia:attribute name="border_width"> + <dia:real val="0.050000000000000003"/> + </dia:attribute> + <dia:attribute name="show_background"> + <dia:boolean val="true"/> + </dia:attribute> + <dia:attribute name="corner_radius"> + <dia:real val="1.1754943508222875e-38"/> + </dia:attribute> + </dia:object> + <dia:group> + <dia:object type="Standard - Box" version="0" id="O1"> + <dia:attribute name="obj_pos"> + <dia:point val="6,8"/> + </dia:attribute> + <dia:attribute name="obj_bb"> + <dia:rectangle val="5.975,7.975;12.025,9.025"/> + </dia:attribute> + <dia:attribute name="elem_corner"> + <dia:point val="6,8"/> + </dia:attribute> + <dia:attribute name="elem_width"> + <dia:real val="6"/> + </dia:attribute> + <dia:attribute name="elem_height"> + <dia:real val="1"/> + </dia:attribute> + <dia:attribute name="border_width"> + <dia:real val="0.050000000000000003"/> + </dia:attribute> + <dia:attribute name="inner_color"> + <dia:color val="#ffff00"/> + </dia:attribute> + <dia:attribute name="show_background"> + <dia:boolean val="true"/> + </dia:attribute> + <dia:attribute name="corner_radius"> + <dia:real val="1.1754943508222875e-38"/> + </dia:attribute> + </dia:object> + <dia:object type="Standard - Text" version="1" id="O2"> + <dia:attribute name="obj_pos"> + <dia:point val="5.95,8.4925"/> + </dia:attribute> + <dia:attribute name="obj_bb"> + <dia:rectangle val="5.95,7.95;10.145,8.89"/> + </dia:attribute> + <dia:attribute name="text"> + <dia:composite type="text"> + <dia:attribute name="string"> + <dia:string>#Gap => Insert#</dia:string> + </dia:attribute> + <dia:attribute name="font"> + <dia:font family="sans" style="0" name="Helvetica"/> + </dia:attribute> + <dia:attribute name="height"> + <dia:real val="0.80000000000000004"/> + </dia:attribute> + <dia:attribute name="pos"> + <dia:point val="5.95,8.4925"/> + </dia:attribute> + <dia:attribute name="color"> + <dia:color val="#000000"/> + </dia:attribute> + <dia:attribute name="alignment"> + <dia:enum val="0"/> + </dia:attribute> + </dia:composite> + </dia:attribute> + <dia:attribute name="valign"> + <dia:enum val="3"/> + </dia:attribute> + </dia:object> + </dia:group> + <dia:group> + <dia:object type="Standard - Box" version="0" id="O3"> + <dia:attribute name="obj_pos"> + <dia:point val="6,2"/> + </dia:attribute> + <dia:attribute name="obj_bb"> + <dia:rectangle val="5.975,1.975;12.025,8.025"/> + </dia:attribute> + <dia:attribute name="elem_corner"> + <dia:point val="6,2"/> + </dia:attribute> + <dia:attribute name="elem_width"> + <dia:real val="6"/> + </dia:attribute> + <dia:attribute name="elem_height"> + <dia:real val="6"/> + </dia:attribute> + <dia:attribute name="border_width"> + <dia:real val="0.050000000000000003"/> + </dia:attribute> + <dia:attribute name="inner_color"> + <dia:color val="#90ee90"/> + </dia:attribute> + <dia:attribute name="show_background"> + <dia:boolean val="true"/> + </dia:attribute> + <dia:attribute name="corner_radius"> + <dia:real val="1.1754943508222875e-38"/> + </dia:attribute> + </dia:object> + <dia:object type="Standard - Text" version="1" id="O4"> + <dia:attribute name="obj_pos"> + <dia:point val="5.975,2.53456"/> + </dia:attribute> + <dia:attribute name="obj_bb"> + <dia:rectangle val="5.975,1.99206;8.91195,2.93206"/> + </dia:attribute> + <dia:attribute name="text"> + <dia:composite type="text"> + <dia:attribute name="string"> + <dia:string>#Processed#</dia:string> + </dia:attribute> + <dia:attribute name="font"> + <dia:font family="sans" style="0" name="Helvetica"/> + </dia:attribute> + <dia:attribute name="height"> + <dia:real val="0.80000000000000004"/> + </dia:attribute> + <dia:attribute name="pos"> + <dia:point val="5.975,2.53456"/> + </dia:attribute> + <dia:attribute name="color"> + <dia:color val="#000000"/> + </dia:attribute> + <dia:attribute name="alignment"> + <dia:enum val="0"/> + </dia:attribute> + </dia:composite> + </dia:attribute> + <dia:attribute name="valign"> + <dia:enum val="3"/> + </dia:attribute> + </dia:object> + </dia:group> + <dia:group> + <dia:object type="Standard - Box" version="0" id="O5"> + <dia:attribute name="obj_pos"> + <dia:point val="6,9"/> + </dia:attribute> + <dia:attribute name="obj_bb"> + <dia:rectangle val="5.975,8.975;12.025,18.025"/> + </dia:attribute> + <dia:attribute name="elem_corner"> + <dia:point val="6,9"/> + </dia:attribute> + <dia:attribute name="elem_width"> + <dia:real val="6"/> + </dia:attribute> + <dia:attribute name="elem_height"> + <dia:real val="9"/> + </dia:attribute> + <dia:attribute name="border_width"> + <dia:real val="0.050000000000000003"/> + </dia:attribute> + <dia:attribute name="inner_color"> + <dia:color val="#ffa500"/> + </dia:attribute> + <dia:attribute name="show_background"> + <dia:boolean val="true"/> + </dia:attribute> + <dia:attribute name="corner_radius"> + <dia:real val="1.1754943508222875e-38"/> + </dia:attribute> + </dia:object> + <dia:object type="Standard - Text" version="1" id="O6"> + <dia:attribute name="obj_pos"> + <dia:point val="5.975,9.53456"/> + </dia:attribute> + <dia:attribute name="obj_bb"> + <dia:rectangle val="5.975,8.99206;11.4275,9.93206"/> + </dia:attribute> + <dia:attribute name="text"> + <dia:composite type="text"> + <dia:attribute name="string"> + <dia:string>#Common => Copy#</dia:string> + </dia:attribute> + <dia:attribute name="font"> + <dia:font family="sans" style="0" name="Helvetica"/> + </dia:attribute> + <dia:attribute name="height"> + <dia:real val="0.80000000000000004"/> + </dia:attribute> + <dia:attribute name="pos"> + <dia:point val="5.975,9.53456"/> + </dia:attribute> + <dia:attribute name="color"> + <dia:color val="#000000"/> + </dia:attribute> + <dia:attribute name="alignment"> + <dia:enum val="0"/> + </dia:attribute> + </dia:composite> + </dia:attribute> + <dia:attribute name="valign"> + <dia:enum val="3"/> + </dia:attribute> + </dia:object> + </dia:group> + <dia:group> + <dia:object type="Standard - Box" version="0" id="O7"> + <dia:attribute name="obj_pos"> + <dia:point val="5,11"/> + </dia:attribute> + <dia:attribute name="obj_bb"> + <dia:rectangle val="4.95,10.95;13.05,15.05"/> + </dia:attribute> + <dia:attribute name="elem_corner"> + <dia:point val="5,11"/> + </dia:attribute> + <dia:attribute name="elem_width"> + <dia:real val="8"/> + </dia:attribute> + <dia:attribute name="elem_height"> + <dia:real val="4"/> + </dia:attribute> + <dia:attribute name="inner_color"> + <dia:color val="#bfbfbf"/> + </dia:attribute> + <dia:attribute name="show_background"> + <dia:boolean val="true"/> + </dia:attribute> + <dia:attribute name="corner_radius"> + <dia:real val="1.1754943508222875e-38"/> + </dia:attribute> + </dia:object> + <dia:object type="Standard - Text" version="1" id="O8"> + <dia:attribute name="obj_pos"> + <dia:point val="4.95,11.9675"/> + </dia:attribute> + <dia:attribute name="obj_bb"> + <dia:rectangle val="4.95,10.95;9.26848,12.71"/> + </dia:attribute> + <dia:attribute name="text"> + <dia:composite type="text"> + <dia:attribute name="string"> + <dia:string>#Window#</dia:string> + </dia:attribute> + <dia:attribute name="font"> + <dia:font family="sans" style="0" name="Helvetica"/> + </dia:attribute> + <dia:attribute name="height"> + <dia:real val="1.5"/> + </dia:attribute> + <dia:attribute name="pos"> + <dia:point val="4.95,11.9675"/> + </dia:attribute> + <dia:attribute name="color"> + <dia:color val="#000000"/> + </dia:attribute> + <dia:attribute name="alignment"> + <dia:enum val="0"/> + </dia:attribute> + </dia:composite> + </dia:attribute> + <dia:attribute name="valign"> + <dia:enum val="3"/> + </dia:attribute> + </dia:object> + </dia:group> + </dia:group> + <dia:group> + <dia:object type="Standard - Box" version="0" id="O9"> + <dia:attribute name="obj_pos"> + <dia:point val="18,2"/> + </dia:attribute> + <dia:attribute name="obj_bb"> + <dia:rectangle val="17.975,1.975;24.025,24.025"/> + </dia:attribute> + <dia:attribute name="elem_corner"> + <dia:point val="18,2"/> + </dia:attribute> + <dia:attribute name="elem_width"> + <dia:real val="6"/> + </dia:attribute> + <dia:attribute name="elem_height"> + <dia:real val="22"/> + </dia:attribute> + <dia:attribute name="border_width"> + <dia:real val="0.050000000000000003"/> + </dia:attribute> + <dia:attribute name="show_background"> + <dia:boolean val="true"/> + </dia:attribute> + <dia:attribute name="corner_radius"> + <dia:real val="1.1754943508222875e-38"/> + </dia:attribute> + </dia:object> + <dia:object type="Standard - Box" version="0" id="O10"> + <dia:attribute name="obj_pos"> + <dia:point val="18,5"/> + </dia:attribute> + <dia:attribute name="obj_bb"> + <dia:rectangle val="17.975,4.975;24.025,14.025"/> + </dia:attribute> + <dia:attribute name="elem_corner"> + <dia:point val="18,5"/> + </dia:attribute> + <dia:attribute name="elem_width"> + <dia:real val="6"/> + </dia:attribute> + <dia:attribute name="elem_height"> + <dia:real val="9"/> + </dia:attribute> + <dia:attribute name="border_width"> + <dia:real val="0.050000000000000003"/> + </dia:attribute> + <dia:attribute name="inner_color"> + <dia:color val="#ffa500"/> + </dia:attribute> + <dia:attribute name="show_background"> + <dia:boolean val="true"/> + </dia:attribute> + <dia:attribute name="corner_radius"> + <dia:real val="1.1754943508222875e-38"/> + </dia:attribute> + </dia:object> + </dia:group> + <dia:group> + <dia:object type="Standard - Text" version="1" id="O11"> + <dia:attribute name="obj_pos"> + <dia:point val="14,9"/> + </dia:attribute> + <dia:attribute name="obj_bb"> + <dia:rectangle val="14,8.4575;16.8122,9.3975"/> + </dia:attribute> + <dia:attribute name="text"> + <dia:composite type="text"> + <dia:attribute name="string"> + <dia:string>#Signature#</dia:string> + </dia:attribute> + <dia:attribute name="font"> + <dia:font family="sans" style="0" name="Helvetica"/> + </dia:attribute> + <dia:attribute name="height"> + <dia:real val="0.80000000000000004"/> + </dia:attribute> + <dia:attribute name="pos"> + <dia:point val="14,9"/> + </dia:attribute> + <dia:attribute name="color"> + <dia:color val="#000000"/> + </dia:attribute> + <dia:attribute name="alignment"> + <dia:enum val="0"/> + </dia:attribute> + </dia:composite> + </dia:attribute> + <dia:attribute name="valign"> + <dia:enum val="3"/> + </dia:attribute> + </dia:object> + <dia:object type="Standard - ZigZagLine" version="1" id="O12"> + <dia:attribute name="obj_pos"> + <dia:point val="12,13"/> + </dia:attribute> + <dia:attribute name="obj_bb"> + <dia:rectangle val="11.95,9;18.05,13.05"/> + </dia:attribute> + <dia:attribute name="orth_points"> + <dia:point val="12,13"/> + <dia:point val="15,13"/> + <dia:point val="15,9.5"/> + <dia:point val="18,9.5"/> + </dia:attribute> + <dia:attribute name="orth_orient"> + <dia:enum val="0"/> + <dia:enum val="1"/> + <dia:enum val="0"/> + </dia:attribute> + <dia:attribute name="autorouting"> + <dia:boolean val="true"/> + </dia:attribute> + <dia:attribute name="end_arrow"> + <dia:enum val="22"/> + </dia:attribute> + <dia:attribute name="end_arrow_length"> + <dia:real val="0.5"/> + </dia:attribute> + <dia:attribute name="end_arrow_width"> + <dia:real val="0.5"/> + </dia:attribute> + </dia:object> + </dia:group> + <dia:group> + <dia:object type="Standard - Text" version="1" id="O13"> + <dia:attribute name="obj_pos"> + <dia:point val="2,8"/> + </dia:attribute> + <dia:attribute name="obj_bb"> + <dia:rectangle val="2,6.9825;4.6625,8.7425"/> + </dia:attribute> + <dia:attribute name="text"> + <dia:composite type="text"> + <dia:attribute name="string"> + <dia:string>#Base#</dia:string> + </dia:attribute> + <dia:attribute name="font"> + <dia:font family="sans" style="0" name="Helvetica"/> + </dia:attribute> + <dia:attribute name="height"> + <dia:real val="1.5"/> + </dia:attribute> + <dia:attribute name="pos"> + <dia:point val="2,8"/> + </dia:attribute> + <dia:attribute name="color"> + <dia:color val="#000000"/> + </dia:attribute> + <dia:attribute name="alignment"> + <dia:enum val="0"/> + </dia:attribute> + </dia:composite> + </dia:attribute> + <dia:attribute name="valign"> + <dia:enum val="3"/> + </dia:attribute> + </dia:object> + <dia:object type="Standard - Line" version="0" id="O14"> + <dia:attribute name="obj_pos"> + <dia:point val="5,8"/> + </dia:attribute> + <dia:attribute name="obj_bb"> + <dia:rectangle val="4.95,7.5;6.05,8.5"/> + </dia:attribute> + <dia:attribute name="conn_endpoints"> + <dia:point val="5,8"/> + <dia:point val="6,8"/> + </dia:attribute> + <dia:attribute name="numcp"> + <dia:int val="1"/> + </dia:attribute> + <dia:attribute name="end_arrow"> + <dia:enum val="22"/> + </dia:attribute> + <dia:attribute name="end_arrow_length"> + <dia:real val="0.5"/> + </dia:attribute> + <dia:attribute name="end_arrow_width"> + <dia:real val="0.5"/> + </dia:attribute> + </dia:object> + </dia:group> + <dia:group> + <dia:object type="Standard - Text" version="1" id="O15"> + <dia:attribute name="obj_pos"> + <dia:point val="1,11"/> + </dia:attribute> + <dia:attribute name="obj_bb"> + <dia:rectangle val="1,9.9825;3.6725,11.7425"/> + </dia:attribute> + <dia:attribute name="text"> + <dia:composite type="text"> + <dia:attribute name="string"> + <dia:string>#Slide#</dia:string> + </dia:attribute> + <dia:attribute name="font"> + <dia:font family="sans" style="0" name="Helvetica"/> + </dia:attribute> + <dia:attribute name="height"> + <dia:real val="1.5"/> + </dia:attribute> + <dia:attribute name="pos"> + <dia:point val="1,11"/> + </dia:attribute> + <dia:attribute name="color"> + <dia:color val="#000000"/> + </dia:attribute> + <dia:attribute name="alignment"> + <dia:enum val="0"/> + </dia:attribute> + </dia:composite> + </dia:attribute> + <dia:attribute name="valign"> + <dia:enum val="3"/> + </dia:attribute> + </dia:object> + <dia:object type="Standard - Line" version="0" id="O16"> + <dia:attribute name="obj_pos"> + <dia:point val="4,11"/> + </dia:attribute> + <dia:attribute name="obj_bb"> + <dia:rectangle val="3.95,10.5;5.05,11.5"/> + </dia:attribute> + <dia:attribute name="conn_endpoints"> + <dia:point val="4,11"/> + <dia:point val="5,11"/> + </dia:attribute> + <dia:attribute name="numcp"> + <dia:int val="1"/> + </dia:attribute> + <dia:attribute name="end_arrow"> + <dia:enum val="22"/> + </dia:attribute> + <dia:attribute name="end_arrow_length"> + <dia:real val="0.5"/> + </dia:attribute> + <dia:attribute name="end_arrow_width"> + <dia:real val="0.5"/> + </dia:attribute> + </dia:object> + </dia:group> + <dia:object type="Standard - Text" version="1" id="O17"> + <dia:attribute name="obj_pos"> + <dia:point val="6,2"/> + </dia:attribute> + <dia:attribute name="obj_bb"> + <dia:rectangle val="6,0.9825;9.38727,2.7425"/> + </dia:attribute> + <dia:attribute name="text"> + <dia:composite type="text"> + <dia:attribute name="string"> + <dia:string>#Target#</dia:string> + </dia:attribute> + <dia:attribute name="font"> + <dia:font family="sans" style="0" name="Helvetica"/> + </dia:attribute> + <dia:attribute name="height"> + <dia:real val="1.5"/> + </dia:attribute> + <dia:attribute name="pos"> + <dia:point val="6,2"/> + </dia:attribute> + <dia:attribute name="color"> + <dia:color val="#000000"/> + </dia:attribute> + <dia:attribute name="alignment"> + <dia:enum val="0"/> + </dia:attribute> + </dia:composite> + </dia:attribute> + <dia:attribute name="valign"> + <dia:enum val="3"/> + </dia:attribute> + </dia:object> + <dia:object type="Standard - Text" version="1" id="O18"> + <dia:attribute name="obj_pos"> + <dia:point val="18,2"/> + </dia:attribute> + <dia:attribute name="obj_bb"> + <dia:rectangle val="18,0.9825;21.3125,2.7425"/> + </dia:attribute> + <dia:attribute name="text"> + <dia:composite type="text"> + <dia:attribute name="string"> + <dia:string>#Origin#</dia:string> + </dia:attribute> + <dia:attribute name="font"> + <dia:font family="sans" style="0" name="Helvetica"/> + </dia:attribute> + <dia:attribute name="height"> + <dia:real val="1.5"/> + </dia:attribute> + <dia:attribute name="pos"> + <dia:point val="18,2"/> + </dia:attribute> + <dia:attribute name="color"> + <dia:color val="#000000"/> + </dia:attribute> + <dia:attribute name="alignment"> + <dia:enum val="0"/> + </dia:attribute> + </dia:composite> + </dia:attribute> + <dia:attribute name="valign"> + <dia:enum val="3"/> + </dia:attribute> + </dia:object> + </dia:group> + </dia:layer> +</dia:diagram>
Modified www/delta_encoder_algorithm.html from [8a9f809ab9] to [75d37d5e32].
@@ -92,28 +92,105 @@ </li> </ol> <a name="processing"><h3>2.1 Processing the target</h3> -<b>... to be completed ... </b> +<p>This, the main phase of the encoder, processes the target in a loop +from beginning to end. The state of the encoder is captured by two +locations, the "base" and the "slide". "base" points to the first byte +of the target for which no delta output has been generated yet, and +"slide" is the location of the window used to look in the "origin" for +commonalities. This window is NHASH bytes long.</p> + +<p>Initially both "base" and "slide" point to the beginning of the +"target". In each iteration of the loop the encoder decides whether to +<ul> +<li>emit a single instruction +to <a href="delta_format.html#copyrange">copy a range</a>, or +</li> +<li>emit two instructions, first +to <a href="delta_format.html#insertlit">insert a literal</a>, then +to <a href="delta_format.html#copyrange">copy a range</a>, or +</li> +<li>move the window forward one byte. +</li> +</ul> +</p> + +<img src="encode10.gif" align="right" hspace="10"> +<p>To make this decision the encoder first computes the hash value for +the NHASH bytes in the window and then looks at all the locations in +the "origin" which have the same signature. This part uses the hash +table created by the pre-processing step to effiently find these +locations.</p> + +<p>For each of the possible candidates the encoder finds the maximal +range of bytes common to both "origin" and "target", going forward and +backward from "slide" in the "target", and the candidate location in +the "origin". This search is constrained on the side of the "target" +by the "base" (backward search), and the end of the "target" (forward +search), and on the side of the "origin" by the beginning and end of +the "origin", respectively.</p> + +<p>From the ranges for all the candidates the best (= largest) common +range is taken and it is determined how many bytes are needed to +encode the bytes between the "base" and the end of that range. If the +range extended back to the "base" then this can be done in a single +copy instruction. Otherwise, i.e if there is a gap between the "base" +and the beginning of the range then two instructions are needed, one +to insert the bytes in the gap as a literal, and a copy instruction +for the range itself. The general situation at this point can be seen +in the picture to the right.</p> + +<p>If the number of bytes needed to encode both gap (if present), and +range is less than the number of bytes we are encoding the encoder +will emit the necessary instructions as described above, set "base" +and "slide" to the end of the encoded range and start the next +iteration at that point.</p> + +<p>If, on the other hand, the encoder either did not find candidate +locations in the origin, or the best range coming out of the search +needed more bytes to encode the range than there were bytes in the +range, then no instructions are emitted and the window is moved one +byte forward. The "base" is left unchanged in that case.</p> + +<p>The processing loop stops at one of two conditions: +<ol> +<li>The encoder decided to move the window forward, but the end of the +window reached the end of the "target". +</li> +<li>After the emission of instructions the new "base" location is +within NHASH bytes of end of the "target", i.e. there are no more than +at most NHASH bytes left. +</li> +</ol> +</p> + +<p>If the processing loop left bytes unencoded, i.e. "base" not +exactly at the end of the "target", as is possible for both end +conditions, then one last insert instruction is emitted to put these +bytes into the delta.<p> <a name="exceptions"><h2>3.0 Exceptions</h2> <p>If the "original" is at most NHASH bytes long no compression of changes is possible, and the segment-list of the delta consists of a single literal which contains the entire "target".</p> +<p>This is actually equivalent to the second end condition of the +processing loop described in the previous section, just checked before +actually entering the loop.</p> <a name="rollhash"><h2>4.0 The rolling hash</h2> <p>The rolling hash described below and used to compute content signatures was chosen not only for good hashing properties, but also to enable the easy (incremental) recalculation of its value for a -sliding window, i.e. where the oldest character is removed from the -window and a new character is shifted in.<p> +sliding window, i.e. where the oldest byte is removed from the window +and a new byte is shifted in.<p> -<a name="rhdef"><h2>4.1 Definition</h2> +<a name="rhdef"><h3>4.1 Definition</h3> <p>Assuming an array Z of NHASH bytes (indexing starting at 0) the hash V is computed via</p> <p align=center><table><tr><td> @@ -123,11 +200,11 @@ </td></tr></table></p> where A and B are unsigned 16-bit integers (hence the <u>mod</u>), and V is a 32-bit unsigned integer with B as MSB, A as LSB. -<a name="rhincr"><h2>4.2 Incremental recalculation</h2> +<a name="rhincr"><h3>4.2 Incremental recalculation</h3> <p>Assuming an array Z of NHASH bytes (indexing starting at 0) with hash V (and components A and B), the dropped byte <img src="encode4.gif" align="center">, and the new byte <img src="encode5.gif" align="center"> , the new hash can
Added www/encode10.gif version [36b56c4055]
cannot compute difference between binary files