[gui-dev] Re: A better QueryRouteTable

Index: com/limegroup/gnutella/routing/QueryRouteTable.java
===================================================================
RCS file: /cvs/core/com/limegroup/gnutella/routing/QueryRouteTable.java,v
retrieving revision 1.47
diff -u -r1.47 QueryRouteTable.java
--- com/limegroup/gnutella/routing/QueryRouteTable.java	4 Nov 2004 19:14:58 -0000	1.47
+++ com/limegroup/gnutella/routing/QueryRouteTable.java	25 Nov 2004 16:10:11 -0000
@@ -160,8 +160,29 @@
         this.sequenceNumber = -1;
         this.sequenceSize = -1;
         this.nextPatch = 0;
-        this.keywordPresent = (byte)(1 - infinity);
-        this.keywordAbsent = (byte)(infinity - 1);
+        if (infinity < 2) {
+            // infinity=1 generates a 1-bit format:
+            this.keywordPresent = (byte)-1;
+            this.keywordAbsent = (byte)0;
+            // However patches are XOR-encoded rather than additive, so that
+            // all changes to present or to absent use the same patch value.
+        } else {
+            // infinity=2 generates a 2-bit format: patch present=-1, absent=1
+            //
+            // infinity=3 generates a 4-bit format: patch present=-2, absent=2
+            // ...
+            // infinity=7 generates a 4-bit format: patch present=-6, absent=6
+            // infinity=8 generates a 4-bit format: patch present=-7, absent=7
+            //
+            // infinity=9 generates a 8-bit format: patch present=-8, absent=8
+            // ...
+            // infinity=15 generates a 8-bit format:patch present=-14,absent=14
+            // ...
+            this.keywordPresent = (byte)(1 - infinity);
+            this.keywordAbsent = (byte)(infinity - 1);
+            // Sent patches are additive, but we only consider their sign
+            // when updating bitTable.
+        }
         this.infinity = infinity;
     }
     
@@ -441,73 +462,63 @@
         //RESET, ensure that m's sequence size matches last message
         if (sequenceSize!=-1 && sequenceSize!=m.getSequenceSize())
             throw new BadPacketException("Inconsistent seq size: "
-                                         +m.getSequenceSize()
-                                         +" vs. "+sequenceSize);
+                                         + m.getSequenceSize()
+                                         + " vs. "+sequenceSize);
         //If we were just reset, ensure that m's sequence number is one.
         //Otherwise it should be one greater than the last message received.
         if (sequenceNumber==-1 ? m.getSequenceNumber()!=1 //reset
                                : sequenceNumber+1!=m.getSequenceNumber())
             throw new BadPacketException("Inconsistent seq number: "
-                                         +m.getSequenceNumber()
-                                         +" vs. "+sequenceNumber);
+                                         + m.getSequenceNumber()
+                                         + " vs. "+sequenceNumber);
 
-        byte[] data=m.getData();
+        byte[] data = m.getData();
 
         //1. Start pipelined uncompression.
         //TODO: check that compression is same as last message.
-        if (m.getCompressor()==PatchTableMessage.COMPRESSOR_DEFLATE) {
+        if (m.getCompressor() == PatchTableMessage.COMPRESSOR_DEFLATE) {
             try {
                 //a) If first message, create uncompressor (if needed).
-                if (m.getSequenceNumber()==1) {
+                if (m.getSequenceNumber() == 1) {
                     uncompressor = new Inflater();
                 }       
                 Assert.that(uncompressor!=null, 
-                    "Null uncompressor.  Sequence: "+m.getSequenceNumber());
-                data=uncompress(data);            
+                    "Null uncompressor.  Sequence: " + m.getSequenceNumber());
+                data = uncompress(data);            
             } catch (IOException e) {
-                throw new BadPacketException("Couldn't uncompress data: "+e);
+                throw new BadPacketException("Couldn't uncompress data: " + e);
             }
         } else if (m.getCompressor()!=PatchTableMessage.COMPRESSOR_NONE) {
             throw new BadPacketException("Unknown compressor");
         }
         
-        //2. Expand nibbles if necessary.
-        if (m.getEntryBits()==4) 
-            data=unhalve(data);
-        else if (m.getEntryBits()!=8)
-            throw new BadPacketException("Unknown value for entry bits");
-
-        //3. Add data[0...] to table[nextPatch...]            
-        for (int i=0; i<data.length; i++) {
-            if(nextPatch >= bitTableLength)
-                throw new BadPacketException("Tried to patch "+nextPatch
-                                             +" on a bitTable of size "
-                                             + bitTableLength);
-            // All negative values indicate presence
-            if (data[i] < 0) {
-                bitTable.set(nextPatch);
-                resizedQRT = null;
-            }
-            // All positive values indicate absence
-            else if (data[i] > 0) {
-                bitTable.clear(nextPatch);
-                resizedQRT = null;
-            }
-            nextPatch++;
-        }
-        bitTable.compact();
-
-        //4. Update sequence numbers.
-        this.sequenceSize=m.getSequenceSize();
-        if (m.getSequenceNumber()!=m.getSequenceSize()) {            
-            this.sequenceNumber=m.getSequenceNumber();
+        //2. Expand nibbles if necessary and apply data[0...] patches
+        // to table[nextPatch...]
+        switch (m.getEntryBits()) {
+        case 8: decode8bits(data); break;
+        case 4: decode4bits(data); break;
+        // /* 2-BIT FORMAT PARSING
+        case 2: decode2bits(data); break;
+        // */
+        // /* 1-BIT FORMAT PARSING
+        case 1: decode1bit(data); break;
+        // */
+        default:
+            throw new BadPacketException("Unknown value " + m.getEntryBits() +
+                                         " for entry bits");
+        }
+        this.bitTable.compact();
+        //3. Update sequence numbers.
+        this.sequenceSize = m.getSequenceSize();
+        if (m.getSequenceNumber() != m.getSequenceSize()) {            
+            this.sequenceNumber = m.getSequenceNumber();
         } else {
             //Sequence complete.
-            this.sequenceNumber=-1;
-            this.sequenceSize=-1;
-            this.nextPatch=0; //TODO: is this right?
+            this.sequenceNumber = -1;
+            this.sequenceSize = -1;
+            this.nextPatch = 0; //TODO: is this right?
             // if this last message was compressed, release the uncompressor.
-            if( this.uncompressor != null ) {
+            if (this.uncompressor != null) {
                 this.uncompressor.end();
                 this.uncompressor = null;
             }
@@ -536,125 +547,406 @@
      */
     public List /* of RouteTableMessage */ encode(
       QueryRouteTable prev, boolean allowCompression) {
-        List /* of RouteTableMessage */ buf=new LinkedList();
-        if (prev==null)
-            buf.add(new ResetTableMessage(bitTableLength, infinity));
-        else
-            Assert.that(prev.bitTableLength==this.bitTableLength,
-                        "TODO: can't deal with tables of different lengths");
-
-        //1. Calculate patch array
-        byte[] data=new byte[bitTableLength];
-        // Fill up data with KEYWORD_NO_CHANGE, since the majority
-        // of elements will be that.
-        // Because it is already filled, we do not need to iterate and
-        // set it anywhere.
-        Utilities.fill(data, 0, bitTableLength, KEYWORD_NO_CHANGE);
-        boolean needsPatch=false;
+        List /* of RouteTableMessage */ buf = new LinkedList();
+        Assert.that(keywordPresent < 0);
+        Assert.that(keywordAbsent > 0 || keywordAbsent == 0 && keywordPresent == -1);
         
-        //1a. If there was a previous table, determine if it was the same one.
-        //    If so, we can prevent BitTableLength calls to BitSet.get(int).
-        if( prev != null ) {
-            //1a-I. If they are not equal, xOr the tables and loop
-            //      through the different bits.  This avoids
-            //      bitTableLength*2 calls to BitSet.get
-            //      at the cost of the xOr'd table's cardinality
-            //      calls to both BitSet.nextSetBit and BitSet.get.
-            //      Generally it is worth it, as our BitTables don't
-            //      change very rapidly.
-            //      With the xOr'd table, we know that all 'clear'
-            //      values have not changed.  Thus, we can use
-            //      nextSetBit on the xOr'd table & this.bitTable.get
-            //      to determine whether or not we should set
-            //      data[x] to keywordPresent or keywordAbsent.
-            //      Because this is an xOr, we know that if 
-            //      this.bitTable.get is true, prev.bitTable.get
-            //      is false, and vice versa.            
-            if(!this.bitTable.equals(prev.bitTable) ) {
-                BitSet xOr = (BitSet)this.bitTable.clone();
-                xOr.xor(prev.bitTable);
-                for (int i=xOr.nextSetBit(0); i >= 0; i=xOr.nextSetBit(i+1)) {
-                    data[i] = this.bitTable.get(i) ?
-                        keywordPresent : keywordAbsent;
-                    needsPatch = true;
-                }
+        //1. Calculate patch array
+        byte[] data;
+        byte bits;
+        if (prev == null) { // No previous table, needs at least a RESET.
+            buf.add(new ResetTableMessage(bitTableLength, infinity));
+            // Check when the current one has no bit set.
+            // If so, just return a single RESET, without any PATCH.
+            if (this.bitTable.nextSetBit(0) < 0)
+                return buf;
+            // /* 1-BIT FORMAT GENERATION
+            if (keywordPresent == -1 && keywordAbsent == 0) {
+               data = encode1bit();
+               bits = 1;
+            } else
+            // */
+            // /* 2-BIT FORMAT GENERATION
+            if (keywordPresent >= -2 && keywordAbsent == 1) {
+               data = encode2bits();
+               bits = 2;
+            } else
+            // */
+            if (keywordPresent >= -8 && keywordAbsent <= 7) {
+                data = encode4bits();
+                bits = 4;
+            } else {
+                data = encode8bits();
+                bits = 8;
             }
-            // Else the two tables are equal, and we don't need to do anything
-            // because all elements already contain KEYWORD_NO_CHANGE.
-        }
-        //1b. If there was no previous table, scan through the table using
-        //    nextSetBit, avoiding bitTableLength calls to BitSet.get(int).
-        else {
-            for (int i=bitTable.nextSetBit(0);i>=0;i=bitTable.nextSetBit(i+1)){
-                data[i] = keywordPresent;
-                needsPatch = true;
+        } else {
+            // Check when the current table equals the previous one.
+            // If so, there's no PATCH to send.
+            Assert.that(prev.bitTableLength == this.bitTableLength,
+                        "TODO: can't deal with tables of different lengths");
+            if (this.bitTable.equals(prev.bitTable))
+                return buf;
+            // /* 1-BIT FORMAT GENERATION
+            if (keywordPresent >= -1 && keywordAbsent <= 0) {
+                data = encode1bit(prev);
+                bits = 1;
+            } else
+            // */
+            // /* 2-BIT FORMAT GENERATION
+            if (keywordPresent >= -2 && keywordAbsent <= 1) {
+                data = encode2bits(prev);
+                bits = 2;
+            } else
+            // */
+            if (keywordPresent >= -8 && keywordAbsent <= 7) {
+                data = encode4bits(prev);
+                bits = 4;
+            } else {
+                data = encode8bits(prev);
+                bits = 8;
             }
         }
-        //Optimization: there's nothing to report.  If prev=null, send a single
-        //RESET.  Otherwise send nothing.
-        if (!needsPatch) {
-            return buf;
-        }
-
-
+        
         //2. Try compression.
-        //TODO: Should this not be done if compression isn't allowed?
-        byte bits=8;
-        // Only halve if our values require 4 signed bytes at most.
-        // keywordPresent will always be negative and
-        // keywordAbsent will always be positive.
-        if( keywordPresent >= -8 && keywordAbsent <= 7 ) {
-            bits = 4;
-            data = halve(data);
-        }
-
-        byte compression=PatchTableMessage.COMPRESSOR_NONE;
-        //Optimization: If we are told it is safe to compress the message,
-        //then attempt to compress it.  Reasons it is not safe include
-        //the outgoing stream already being compressed.
-        if( allowCompression ) {
+        byte compression = PatchTableMessage.COMPRESSOR_NONE;
+        // Optimization: If we are told it is safe to compress the message,
+        // then attempt to compress it. Reasons it is not safe include the
+        // outgoing stream already being compressed.
+        if (allowCompression) {
             byte[] patchCompressed = IOUtils.deflate(data);
-            if (patchCompressed.length<data.length) {
-                //...Hooray!  Compression was efficient.
-                data=patchCompressed;
-                compression=PatchTableMessage.COMPRESSOR_DEFLATE;
+            if (patchCompressed.length < data.length) {
+                data = patchCompressed; // Compression was efficient!
+                compression = PatchTableMessage.COMPRESSOR_DEFLATE;
             }
         }
-                   
-
-        //3. Break into 1KB chunks and send.  TODO: break size limits if needed.
-        final int chunks=(int)Math.ceil((float)data.length/(float)MAX_PATCH_SIZE);
-        int chunk=1;
-        for (int i=0; i<data.length; i+=MAX_PATCH_SIZE) {
-            //Just past the last position of data to copy.
-            //Note special case for last chunk.  
-            int stop=Math.min(i+MAX_PATCH_SIZE, data.length);
+        
+        //3. Break into 1KB chunks and send. TODO: break size limits if needed.
+        //final int chunks = (int)Math.ceil((float)data.length/(float)MAX_PATCH_SIZE);
+        final int chunks = (data.length - 1) / MAX_PATCH_SIZE + 1;
+        int chunk = 1, start = 0, stop = MAX_PATCH_SIZE;
+        while (stop <= data.length) {
+            buf.add(new PatchTableMessage((short)chunk++, (short)chunks,
+                                          compression, bits,
+                                          data, start, stop));
+            start = stop;
+            stop += MAX_PATCH_SIZE;
+        }
+        if (start < data.length)
             buf.add(new PatchTableMessage((short)chunk, (short)chunks,
                                           compression, bits,
-                                          data, i, stop));
-            chunk++;
-        }        
+                                          data, start, data.length));
         return buf;        
     }
 
-
     ///////////////// Helper Functions for Codec ////////////////////////
 
-    /** Returns the uncompressed version of the given defalted bytes, using
+    private byte[] encode8bits() {
+        final BitSet bs = this.bitTable;
+        final byte[] data = new byte[this.bitTableLength];
+        Utilities.fill(data, 0, data.length, KEYWORD_NO_CHANGE);
+        //TODO: do we still need parametered infinity?
+        //      shouldn't we fix to present=-7, absent=7?
+        final byte present = this.keywordPresent;
+        for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1))
+            data[i] = present;
+        return data;
+    }
+
+    private byte[] encode8bits(final QueryRouteTable prev) {
+        final BitSet bs = this.bitTable;
+        final byte[] data = new byte[this.bitTableLength];
+        Utilities.fill(data, 0, data.length, KEYWORD_NO_CHANGE);
+        final BitSet xOr = (BitSet)bs.clone();
+        xOr.xor(prev.bitTable);
+        //TODO: do we still need parametered infinity?
+        //      shouldn't we fix to present=-7, absent=7?
+        final byte present = this.keywordPresent;
+        final byte absent = this.keywordAbsent;
+        for (int i = xOr.nextSetBit(0); i >= 0; i = xOr.nextSetBit(i + 1))
+            data[i] = bs.get(i) ? present : absent;
+        return data;
+    }
+
+    private byte[] encode4bits() {
+        final BitSet bs = this.bitTable;
+        final byte[] data = new byte[(this.bitTableLength + 1) >> 1];
+        Utilities.fill(data, 0, data.length, KEYWORD_NO_CHANGE);
+        //TODO: do we still need parametered infinity?
+        //      shouldn't we fix to present=-7, absent=7?
+        final byte present1 = (byte)(this.keywordPresent & 0x0F);
+        final byte present0 = (byte)(present1 << 4);
+        for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1)) {
+            if ((i & 1) == 0) // even position, set first high nibble
+                data[i>>1]  = present0;
+            else // odd position, set low nibble
+                data[i>>1] |= present1;
+        }
+        return data;
+    }
+
+    private byte[] encode4bits(final QueryRouteTable prev) {
+        final BitSet bs = this.bitTable;
+        final BitSet xOr = (BitSet)bs.clone();
+        xOr.xor(prev.bitTable);
+        final byte[] data = new byte[(this.bitTableLength + 1) >> 1];
+        Utilities.fill(data, 0, data.length, KEYWORD_NO_CHANGE);
+        //TODO: do we still need parametered infinity?
+        //      shouldn't we fix to present=-7, absent=7?
+        final byte present1 = (byte)(this.keywordPresent & 0x0F);
+        final byte present0 = (byte)(present1 << 4);
+        final byte absent1 = (byte)(this.keywordAbsent & 0x0F);
+        final byte absent0 = (byte)(absent1 << 4);
+        for (int i = xOr.nextSetBit(0); i >= 0; i = xOr.nextSetBit(i + 1)) {
+            if ((i & 1) == 0) // even position, set first high nibble
+                data[i>>1]  = bs.get(i) ? present0 : absent0;
+            else // odd position, set low nibble
+                data[i>>1] |= bs.get(i) ? present1 : absent1;
+        }
+        return data;
+    }
+
+    private byte[] encode2bits() {
+        BitSet bs = this.bitTable;
+        byte[] data = new byte[(this.bitTableLength + 3) >> 2];
+        Utilities.fill(data, 0, data.length, KEYWORD_NO_CHANGE);
+        // Note: on 2 bits, keywordPresent could only be -2 or -1, and
+        // keywordAbsent = 1. We can only use infinite=1, so let's use:
+        // keywordPresent = -1(mod 3) = 3, keywordAbsent = 1(mod 3) = 1
+        //byte present3 = this.keywordPresent & 0x03; //-1(mod3)=0x03
+        //byte present2 = (byte)(present3 << 2);//0x0c
+        //byte present1 = (byte)(present3 << 4);//0x30
+        //byte present0 = (byte)(present3 << 6);//0xc0
+        for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1)) {
+            switch (i & 3) {
+            case 0: data[i>>2]  = (byte)0xc0; break;//present0
+            case 1: data[i>>2] |= (byte)0x30; break;//present1
+            case 2: data[i>>2] |= (byte)0x0c; break;//present2
+            case 3: data[i>>2] |= (byte)0x03; break;//present3
+            }
+        }
+        return data;
+    }
+
+    private byte[] encode2bits(final QueryRouteTable prev) {
+        final BitSet bs = this.bitTable;
+        final BitSet xOr = (BitSet)bs.clone();
+        xOr.xor(prev.bitTable);
+        final byte[] data = new byte[(this.bitTableLength + 3) >> 2];
+        Utilities.fill(data, 0, data.length, KEYWORD_NO_CHANGE);
+        // Note: on 2 bits, keywordPresent could only be -2 or -1, and
+        // keywordAbsent = 1. We can only use infinite = 1, so let's use:
+        // keywordPresent = -1(mod 3), keywordAbsent = 1(mod 3)
+        //byte present3 = this.keywordPresent & 0x03; //-1(mod3)=0x03
+        //byte present2 = (byte)(present3 << 2);//0x0c
+        //byte present1 = (byte)(present3 << 4);//0x30
+        //byte present0 = (byte)(present3 << 6);//0xc0
+        //byte absent3 = this.keywordAbsent & 0x03; // 0x01
+        //byte absent2 = (byte)(absent3 << 2);// 0x04
+        //byte absent1 = (byte)(absent3 << 4);// 0x10
+        //byte absent0 = (byte)(absent3 << 6);// 0x40
+        for (int i = xOr.nextSetBit(0); i >= 0; i = xOr.nextSetBit(i + 1)) {
+            switch (i & 3) {
+            case 0: data[i>>2]  = bs.get(i) ? (byte)0xc0 : (byte)0x40; break;//?present0:absent0
+            case 1: data[i>>2] |= bs.get(i) ? (byte)0x30 : (byte)0x10; break;//?present1:absent1
+            case 2: data[i>>2] |= bs.get(i) ? (byte)0x0c : (byte)0x04; break;//?present2:absent2
+            case 3: data[i>>2] |= bs.get(i) ? (byte)0x03 : (byte)0x01; break;//?present3:absent3
+            }
+        }
+        return data;
+    }
+
+    private byte[] encode1bit() {
+        final BitSet bs = this.bitTable;
+        final byte[] data = new byte[(this.bitTableLength + 7) >> 3];
+        Utilities.fill(data, 0, data.length, KEYWORD_NO_CHANGE);
+        // We don't encode present or absent but only which bits changed.
+        // infinity can only be 1, present=-1, absent=0
+        for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1))
+            data[i>>3] |= (byte)(0x80 >> (i & 7));
+        return data;
+    }
+
+    private byte[] encode1bit(final QueryRouteTable prev) {
+        final BitSet bs = this.bitTable;
+        final BitSet xOr = (BitSet)bs.clone();
+        xOr.xor(prev.bitTable);
+        final byte[] data = new byte[(this.bitTableLength + 7) >> 3];
+        Utilities.fill(data, 0, data.length, KEYWORD_NO_CHANGE);
+        // We don't encode present or absent but only which bits changed.
+        // infinity can only be 1, change(present/absent)=-1, unchanged=0
+        for (int i = xOr.nextSetBit(0); i >= 0; i = xOr.nextSetBit(i + 1))
+            data[i>>3] |= (byte)(0x80 >> (i & 7));
+        return data;
+    }
+
+    private void decode8bits(byte[] data) throws BadPacketException {
+        final BitSet bs = this.bitTable;
+        final int bsLen = this.bitTableLength;
+        int j = this.nextPatch;
+        if (j + data.length > bsLen)
+            throw new BadPacketException("Tried to patch "
+                                         + (j + data.length - 1)
+                                         + " on a bitTable of size "
+                                         + bsLen);
+        for (int i = 0; i < data.length; i++) {
+            // all zeroes indicate no change
+            final byte b;
+            if ((b = data[i]) != 0) {
+                // the patch is non-zero (changed)
+                // All negative values indicate change to presence
+                // All positive values indicate change to absence
+                if (b < 0)
+                    bs.set(j);
+                else
+                    bs.clear(j);
+                resizedQRT = null;
+            }
+            j++;
+        }
+        this.nextPatch = j;
+    }
+    
+    private void decode4bits(byte[] data) throws BadPacketException {
+        final BitSet bs = this.bitTable;
+        final int bsLen = this.bitTableLength;
+        int j = this.nextPatch;
+        if (j + data.length * 2 > bsLen)
+            throw new BadPacketException("Tried to patch "
+                                         + (j + data.length * 2 - 1)
+                                         + " on a bitTable of size "
+                                         + bsLen);
+        for (int i = 0; i < data.length; i++) {
+            // all zeroes indicate no change
+            final byte b;
+            if ((b = data[i]) != 0) {
+                // at least one of the two patches is non-zero (changed)
+                // test if first (high) patch is non-zero (changed)
+                if ((b & 0xf0) != 0) {
+                    // All negative values indicate change to presence
+                    // All positive values indicate change to absence
+                    if (b < 0)
+                        bs.set(j);
+                    else
+                        bs.clear(j);
+                }
+                // test if second (low) patch is non-zero (changed)
+                if ((b & 0x0f) != 0) {
+                    // All negative values indicate change to presence
+                    // All positive values indicate change to absence
+                    if ((b & 0x08) != 0)//just check the nibble sign bit
+                        bs.set(j + 1);
+                    else
+                        bs.clear(j + 1);
+                }
+                resizedQRT = null;
+            }
+            j += 2;
+        }
+        this.nextPatch = j;
+    }
+    
+    private void decode2bits(byte[] data) throws BadPacketException {
+        final BitSet bs = this.bitTable;
+        final int bsLen = this.bitTableLength;
+        int j = this.nextPatch;
+        if (j + data.length * 4 > bsLen)
+            throw new BadPacketException("Tried to patch "
+                                         + (j + data.length * 4 - 1)
+                                         + " on a bitTable of size "
+                                         + bsLen);
+        for (int i = 0; i < data.length; i++) {
+            // all zeroes indicate no change
+            final byte b;
+            if ((b = data[i]) != 0) {
+                // at least one of the four patches is non-zero (changed)
+                // test if first (high) patch is non-zero (changed)
+                if ((b & 0xc0) != 0) {
+                    // All negative values indicate change to presence
+                    // All positive values indicate change to absence
+                    if (b < 0)
+                        bs.set(j);
+                    else
+                        bs.clear(j);
+                }
+                // test if second patch is non-zero (changed)
+                if ((b & 0x30) != 0) {
+                    // All negative values indicate change to presence
+                    // All positive values indicate change to absence
+                    if ((b & 0x20) != 0)//just check the high sign bit
+                        bs.set(j + 1);
+                    else
+                        bs.clear(j + 1);
+                }
+                // test if third patch is non-zero (changed)
+                if ((b & 0x0c) != 0) {
+                    // All negative values indicate change to presence
+                    // All positive values indicate change to absence
+                    if ((b & 0x08) != 0)//just check the high sign bit
+                        bs.set(j + 2);
+                    else
+                        bs.clear(j + 2);
+                }
+                // test if fourth (low) patch is non-zero (changed)
+                if ((b & 0x03) != 0) {
+                    // All negative values indicate change to presence
+                    // All positive values indicate change to absence
+                    if ((b & 0x02) != 0)//just check the high sign bit
+                        bs.set(j + 3);
+                    else
+                        bs.clear(j + 3);
+                }
+                resizedQRT = null;
+            }
+            j += 4;
+        }
+        this.nextPatch = j;
+    }
+    
+    private void decode1bit(byte[] data) throws BadPacketException {
+        final BitSet bs = this.bitTable;
+        final int bsLen = this.bitTableLength;
+        int j = this.nextPatch;
+        if (j + data.length * 8 > bsLen)
+            throw new BadPacketException("Tried to patch "
+                                         + (j + data.length * 8 - 1)
+                                         + " on a bitTable of size "
+                                         + bsLen);
+        for (int i = 0; i < data.length; i++) {
+            final byte b;
+            // all zeroes indicate no change
+            if ((b = data[i]) != 0) {
+                // at least one of the eight patches is non-zero (changed)
+                // test each non-zero bit to flip corresponding bits in bs.
+                if ((b & 0x80) != 0) bs.flip(j);
+                if ((b & 0x40) != 0) bs.flip(j + 1);
+                if ((b & 0x20) != 0) bs.flip(j + 2);
+                if ((b & 0x10) != 0) bs.flip(j + 3);
+                if ((b & 0x08) != 0) bs.flip(j + 4);
+                if ((b & 0x04) != 0) bs.flip(j + 5);
+                if ((b & 0x02) != 0) bs.flip(j + 6);
+                if ((b & 0x01) != 0) bs.flip(j + 7);
+                resizedQRT = null;
+            }
+            j += 8;
+        }
+        this.nextPatch = j;
+    }
+    
+    /** Returns the uncompressed version of the given defaulted bytes, using
      *  any dictionaries in uncompressor.  Throws IOException if the data is
      *  corrupt.
      *      @requires inflater initialized 
      *      @modifies inflater */
     private byte[] uncompress(byte[] data) throws IOException {
-        ByteArrayOutputStream baos=new ByteArrayOutputStream();
+        ByteArrayOutputStream baos = new ByteArrayOutputStream();
         uncompressor.setInput(data);
         
         try {
-            byte[] buf=new byte[1024];
+            byte[] buf = new byte[1024];
             while (true) {
-                int read=uncompressor.inflate(buf);
+                int read = uncompressor.inflate(buf);
                 //Needs input?
-                if (read==0)
+                if (read == 0)
                     break;
                 baos.write(buf, 0, read);                
             }
@@ -664,38 +956,45 @@
             throw new IOException("Bad deflate format");
         }
     }
-
     
-    /** Returns an array R of length array.length/2, where R[i] consists of the
-     *  low nibble of array[2i] concatentated with the low nibble of array[2i+1].
-     *  Note that unhalve(halve(array))=array if all elements of array fit can 
-     *  fit in four signed bytes.
-     *      @requires array.length is a multiple of two */
+    /** NO MORE NEEDED, EXCEPT FOR THE TESTS MODULE
+     * Returns an array R of length array.length/2, where R[i] consists of the
+     * low nibble of array[2i] concatentated with the low nibble of array[2i+1].
+     * Note that unhalve(halve(array))=array if all elements of array fit can
+     * fit in two signed bytes.
+     * @requires array.length is a multiple of two */
     static byte[] halve(byte[] array) {
-        byte[] ret=new byte[array.length/2];
-        for (int i=0; i<ret.length; i++)
-            ret[i]=(byte)((array[2*i]<<4) | (array[2*i+1]&0xF));
+        final byte[] ret = new byte[array.length >> 1];
+        for (int i = 0, j = 0; i < ret.length; ++i, j += 2)
+            ret[i] = (byte)((array[j] << 4) | (array[j + 1] & 15));
         return ret;
     }
 
-    /** Returns an array of R of length array.length*2, where R[i] is the the
-     *  sign-extended high nibble of floor(i/2) if i even, or the sign-extended
-     *  low nibble of floor(i/2) if i odd. */        
+    /** NO MORE NEEDED, EXCEPT FOR THE TESTS MODULE
+     * Returns an array of R of length array.length * 2, where R[i] is the
+     * sign-extended high nibble of floor(i/2) if i even, or the sign-extended
+     * low nibble of floor(i/2) if i odd.
+     * Note that only the sign or zeroness of unhalved elements is considered
+     * when decoding patches, so there's only 2 significant bits per element.
+     */        
     static byte[] unhalve(byte[] array) {
-        byte[] ret=new byte[array.length*2];
-        for (int i=0; i<array.length; i++) {
-            ret[2*i]=(byte)(array[i]>>4);     //sign extension
-            ret[2*i+1]=extendNibble((byte)(array[i]&0xF));
+        final byte[] ret = new byte[array.length << 1];
+        for (int i = 0, j = 0; i < array.length; ++i, j += 2) {
+            byte b;
+            ret[j] = (byte)((b = array[i]) >> 4); //sign extension
+            ret[j + 1] = (byte)(((b & 8) == 0) ? (b & 7) : (b | -8));
         }
         return ret;
     }    
     
-    /** Sign-extends the low nibble of b, i.e., 
-     *  returns (from MSB to LSB) b[3]b[3]b[3]b[3]b[3]b[2]b[1]b[0]. */
+    /** NO MORE NEEDED, EXCEPT FOR THE TESTS MODULE
+     * Sign-extends the low nibble of b, i.e., 
+     *  returns (from MSB to LSB) b[3]b[3]b[3]b[3]b[3]b[2]b[1]b[0].
+     */
     static byte extendNibble(byte b) {
-        if ((b&0x8)!=0)   //negative nibble; sign-extend.
-            return (byte)(0xF0 | b);
+        if ((b & 8) == 0)
+            return (byte)(b & 7);
         else
-            return b;        
+            return (byte)(b | -8);
     }
 }