< prev index next >

src/jdk.incubator.httpclient/share/classes/jdk/incubator/http/internal/hpack/Huffman.java

Print this page


   1 /*
   2  * Copyright (c) 2014, 2016, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 package jdk.incubator.http.internal.hpack;
  26 
  27 import java.io.IOException;
  28 import java.io.UncheckedIOException;
  29 import java.nio.ByteBuffer;
  30 
  31 import static java.lang.String.format;
  32 
  33 /**
  34  * Huffman coding table.
  35  *
  36  * <p> Instances of this class are safe for use by multiple threads.
  37  *
  38  * @since 9
  39  */
  40 public final class Huffman {
  41 
  42     // TODO: check if reset is done in both reader and writer
  43 
  44     static final class Reader {
  45 
  46         private Node curr; // position in the trie
  47         private int len;   // length of the path from the root to 'curr'
  48         private int p;     // byte probe
  49 
  50         {
  51             reset();
  52         }
  53 
  54         public void read(ByteBuffer source, Appendable destination,
  55                          boolean isLast) {

  56             read(source, destination, true, isLast);
  57         }
  58 
  59         // Takes 'isLast' rather than returns whether the reading is done or
  60         // not, for more informative exceptions.
  61         void read(ByteBuffer source, Appendable destination, boolean reportEOS,
  62                   boolean isLast) {
  63 

  64             Node c = curr;
  65             int l = len;
  66             /*
  67                Since ByteBuffer is itself stateful, its position is
  68                remembered here NOT as a part of Reader's state,
  69                but to set it back in the case of a failure
  70              */
  71             int pos = source.position();
  72 
  73             while (source.hasRemaining()) {
  74                 int d = source.get();
  75                 for (; p != 0; p >>= 1) {
  76                     c = c.getChild(p & d);
  77                     l++;
  78                     if (c.isLeaf()) {
  79                         if (reportEOS && c.isEOSPath) {
  80                             throw new IllegalArgumentException("Encountered EOS");
  81                         }

  82                         try {
  83                             destination.append(c.getChar());
  84                         } catch (RuntimeException | Error e) {
  85                             source.position(pos);
  86                             throw e;



  87                         } catch (IOException e) {
  88                             source.position(pos);
  89                             throw new UncheckedIOException(e);
  90                         }
  91                         c = INSTANCE.root;
  92                         l = 0;
  93                     }
  94                     curr = c;
  95                     len = l;
  96                 }
  97                 resetProbe();
  98                 pos++;
  99             }
 100             if (!isLast) {
 101                 return; // it's too early to jump to any conclusions, let's wait
 102             }
 103             if (c.isLeaf()) {
 104                 return; // it's perfectly ok, no extra padding bits
 105             }
 106             if (c.isEOSPath && len <= 7) {
 107                 return; // it's ok, some extra padding bits
 108             }
 109             if (c.isEOSPath) {
 110                 throw new IllegalArgumentException(
 111                         "Padding is too long (len=" + len + ") " +
 112                                 "or unexpected end of data");
 113             }
 114             throw new IllegalArgumentException(
 115                     "Not a EOS prefix padding or unexpected end of data");
 116         }
 117 
 118         public void reset() {
 119             curr = INSTANCE.root;
 120             len = 0;
 121             resetProbe();
 122         }
 123 
 124         private void resetProbe() {
 125             p = 0x80;
 126         }
 127     }
 128 
 129     static final class Writer {
 130 
 131         private int pos;       // position in 'source'
 132         private int avail = 8; // number of least significant bits available in 'curr'
 133         private int curr;      // next byte to put to the destination
 134         private int rem;       // number of least significant bits in 'code' yet to be processed


 492     public int lengthOf(CharSequence value) {
 493         return lengthOf(value, 0, value.length());
 494     }
 495 
 496     /**
 497      * Calculates the number of bytes required to represent a subsequence of the
 498      * given {@code CharSequence} with the Huffman coding.
 499      *
 500      * @param value
 501      *         characters
 502      * @param start
 503      *         the start index, inclusive
 504      * @param end
 505      *         the end index, exclusive
 506      *
 507      * @return number of bytes
 508      *
 509      * @throws NullPointerException
 510      *         if the value is null
 511      * @throws IndexOutOfBoundsException
 512      *         if any invocation of {@code value.charAt(i)}, where {@code start
 513      *         <= i < end} would throw an IndexOutOfBoundsException
 514      */
 515     public int lengthOf(CharSequence value, int start, int end) {
 516         int len = 0;
 517         for (int i = start; i < end; i++) {
 518             char c = value.charAt(i);
 519             len += INSTANCE.codeOf(c).length;
 520         }
 521         // Integer division with ceiling, assumption:
 522         assert (len / 8 + (len % 8 != 0 ? 1 : 0)) == (len + 7) / 8 : len;
 523         return (len + 7) / 8;
 524     }
 525 
 526     private void addChar(int c, int code, int bitLength) {
 527         addLeaf(c, code, bitLength, false);
 528         codes[c] = new Code(code, bitLength);
 529     }
 530 
 531     private void addEOS(int c, int code, int bitLength) {
 532         addLeaf(c, code, bitLength, true);
 533         codes[c] = new Code(code, bitLength);


   1 /*
   2  * Copyright (c) 2014, 2017, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 package jdk.incubator.http.internal.hpack;
  26 
  27 import java.io.IOException;

  28 import java.nio.ByteBuffer;
  29 
  30 import static java.lang.String.format;
  31 
  32 /**
  33  * Huffman coding table.
  34  *
  35  * <p> Instances of this class are safe for use by multiple threads.
  36  *
  37  * @since 9
  38  */
  39 public final class Huffman {
  40 
  41     // TODO: check if reset is done in both reader and writer
  42 
  43     static final class Reader {
  44 
  45         private Node curr; // position in the trie
  46         private int len;   // length of the path from the root to 'curr'
  47         private int p;     // byte probe
  48 
  49         {
  50             reset();
  51         }
  52 
  53         public void read(ByteBuffer source,
  54                          Appendable destination,
  55                          boolean isLast) throws IOException {
  56             read(source, destination, true, isLast);
  57         }
  58 
  59         // Takes 'isLast' rather than returns whether the reading is done or
  60         // not, for more informative exceptions.
  61         void read(ByteBuffer source,
  62                   Appendable destination,
  63                   boolean reportEOS, /* reportEOS is exposed for tests */
  64                   boolean isLast) throws IOException {
  65             Node c = curr;
  66             int l = len;
  67             /*
  68                Since ByteBuffer is itself stateful, its position is
  69                remembered here NOT as a part of Reader's state,
  70                but to set it back in the case of a failure
  71              */
  72             int pos = source.position();
  73 
  74             while (source.hasRemaining()) {
  75                 int d = source.get();
  76                 for (; p != 0; p >>= 1) {
  77                     c = c.getChild(p & d);
  78                     l++;
  79                     if (c.isLeaf()) {
  80                         if (reportEOS && c.isEOSPath) {
  81                             throw new IOException("Encountered EOS");
  82                         }
  83                         char ch;
  84                         try {
  85                             ch = c.getChar();
  86                         } catch (IllegalStateException e) {
  87                             source.position(pos); // do we need this?
  88                             throw new IOException(e);
  89                         }
  90                         try {
  91                             destination.append(ch);
  92                         } catch (IOException e) {
  93                             source.position(pos); // do we need this?
  94                             throw e;
  95                         }
  96                         c = INSTANCE.root;
  97                         l = 0;
  98                     }
  99                     curr = c;
 100                     len = l;
 101                 }
 102                 resetProbe();
 103                 pos++;
 104             }
 105             if (!isLast) {
 106                 return; // it's too early to jump to any conclusions, let's wait
 107             }
 108             if (c.isLeaf()) {
 109                 return; // it's perfectly ok, no extra padding bits
 110             }
 111             if (c.isEOSPath && len <= 7) {
 112                 return; // it's ok, some extra padding bits
 113             }
 114             if (c.isEOSPath) {
 115                 throw new IOException(
 116                         "Padding is too long (len=" + len + ") " +
 117                                 "or unexpected end of data");
 118             }
 119             throw new IOException(
 120                     "Not a EOS prefix padding or unexpected end of data");
 121         }
 122 
 123         public void reset() {
 124             curr = INSTANCE.root;
 125             len = 0;
 126             resetProbe();
 127         }
 128 
 129         private void resetProbe() {
 130             p = 0x80;
 131         }
 132     }
 133 
 134     static final class Writer {
 135 
 136         private int pos;       // position in 'source'
 137         private int avail = 8; // number of least significant bits available in 'curr'
 138         private int curr;      // next byte to put to the destination
 139         private int rem;       // number of least significant bits in 'code' yet to be processed


 497     public int lengthOf(CharSequence value) {
 498         return lengthOf(value, 0, value.length());
 499     }
 500 
 501     /**
 502      * Calculates the number of bytes required to represent a subsequence of the
 503      * given {@code CharSequence} with the Huffman coding.
 504      *
 505      * @param value
 506      *         characters
 507      * @param start
 508      *         the start index, inclusive
 509      * @param end
 510      *         the end index, exclusive
 511      *
 512      * @return number of bytes
 513      *
 514      * @throws NullPointerException
 515      *         if the value is null
 516      * @throws IndexOutOfBoundsException
 517      *         if any invocation of {@code value.charAt(i)}, where
 518      *         {@code start <= i < end} would throw an IndexOutOfBoundsException
 519      */
 520     public int lengthOf(CharSequence value, int start, int end) {
 521         int len = 0;
 522         for (int i = start; i < end; i++) {
 523             char c = value.charAt(i);
 524             len += INSTANCE.codeOf(c).length;
 525         }
 526         // Integer division with ceiling, assumption:
 527         assert (len / 8 + (len % 8 != 0 ? 1 : 0)) == (len + 7) / 8 : len;
 528         return (len + 7) / 8;
 529     }
 530 
 531     private void addChar(int c, int code, int bitLength) {
 532         addLeaf(c, code, bitLength, false);
 533         codes[c] = new Code(code, bitLength);
 534     }
 535 
 536     private void addEOS(int c, int code, int bitLength) {
 537         addLeaf(c, code, bitLength, true);
 538         codes[c] = new Code(code, bitLength);


< prev index next >