content: /*
   ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
   ~                                                                               ~
   ~ The MIT License (MIT)                                                         ~
   ~                                                                               ~
   ~ Copyright (c) 2015-2025 miaixz.org and other contributors.                    ~
   ~                                                                               ~
   ~ Permission is hereby granted, free of charge, to any person obtaining a copy  ~
   ~ of this software and associated documentation files (the "Software"), to deal ~
   ~ in the Software without restriction, including without limitation the rights  ~
   ~ to use, copy, modify, merge, publish, distribute, sublicense, and/or sell     ~
   ~ copies of the Software, and to permit persons to whom the Software is         ~
   ~ furnished to do so, subject to the following conditions:                      ~
   ~                                                                               ~
   ~ The above copyright notice and this permission notice shall be included in    ~
   ~ all copies or substantial portions of the Software.                           ~
   ~                                                                               ~
   ~ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR    ~
   ~ IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,      ~
   ~ FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE   ~
   ~ AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER        ~
   ~ LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, ~
   ~ OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN     ~
   ~ THE SOFTWARE.                                                                 ~
   ~                                                                               ~
   ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
  */
  package org.miaixz.bus.http.metric.http;
  
  import java.io.ByteArrayOutputStream;
  import java.io.IOException;
  
  import org.miaixz.bus.core.io.ByteString;
  import org.miaixz.bus.core.io.sink.BufferSink;
  import org.miaixz.bus.core.lang.Normal;
  
  /**
   * 这个类最初是由以下类组成的<a href="https://github.com/twitter/hpack">Twitter Hpack</a>.
   *
   * <ul>
   * <li>{@code com.twitter.hpack.HuffmanEncoder}</li>
   * <li>{@code com.twitter.hpack.HuffmanDecoder}</li>
   * <li>{@code com.twitter.hpack.HpackUtil}</li>
   * </ul>
   *
   * @author Kimi Liu
   * @since Java 17+
   */
  public class Huffman {
  
      private static final int[] CODES = { 0x1ff8, 0x7fffd8, 0xfffffe2, 0xfffffe3, 0xfffffe4, 0xfffffe5, 0xfffffe6,
              0xfffffe7, 0xfffffe8, 0xffffea, 0x3ffffffc, 0xfffffe9, 0xfffffea, 0x3ffffffd, 0xfffffeb, 0xfffffec,
              0xfffffed, 0xfffffee, 0xfffffef, 0xffffff0, 0xffffff1, 0xffffff2, 0x3ffffffe, 0xffffff3, 0xffffff4,
              0xffffff5, 0xffffff6, 0xffffff7, 0xffffff8, 0xffffff9, 0xffffffa, 0xffffffb, 0x14, 0x3f8, 0x3f9, 0xffa,
              0x1ff9, 0x15, 0xf8, 0x7fa, 0x3fa, 0x3fb, 0xf9, 0x7fb, 0xfa, 0x16, 0x17, 0x18, 0x0, 0x1, 0x2, 0x19, 0x1a,
              0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x5c, 0xfb, 0x7ffc, 0x20, 0xffb, 0x3fc, 0x1ffa, 0x21, 0x5d, 0x5e, 0x5f, 0x60,
              0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, 0x70, 0x71, 0x72,
              0xfc, 0x73, 0xfd, 0x1ffb, 0x7fff0, 0x1ffc, 0x3ffc, 0x22, 0x7ffd, 0x3, 0x23, 0x4, 0x24, 0x5, 0x25, 0x26,
              0x27, 0x6, 0x74, 0x75, 0x28, 0x29, 0x2a, 0x7, 0x2b, 0x76, 0x2c, 0x8, 0x9, 0x2d, 0x77, 0x78, 0x79, 0x7a,
              0x7b, 0x7ffe, 0x7fc, 0x3ffd, 0x1ffd, 0xffffffc, 0xfffe6, 0x3fffd2, 0xfffe7, 0xfffe8, 0x3fffd3, 0x3fffd4,
              0x3fffd5, 0x7fffd9, 0x3fffd6, 0x7fffda, 0x7fffdb, 0x7fffdc, 0x7fffdd, 0x7fffde, 0xffffeb, 0x7fffdf,
              0xffffec, 0xffffed, 0x3fffd7, 0x7fffe0, 0xffffee, 0x7fffe1, 0x7fffe2, 0x7fffe3, 0x7fffe4, 0x1fffdc,
              0x3fffd8, 0x7fffe5, 0x3fffd9, 0x7fffe6, 0x7fffe7, 0xffffef, 0x3fffda, 0x1fffdd, 0xfffe9, 0x3fffdb, 0x3fffdc,
              0x7fffe8, 0x7fffe9, 0x1fffde, 0x7fffea, 0x3fffdd, 0x3fffde, 0xfffff0, 0x1fffdf, 0x3fffdf, 0x7fffeb,
              0x7fffec, 0x1fffe0, 0x1fffe1, 0x3fffe0, 0x1fffe2, 0x7fffed, 0x3fffe1, 0x7fffee, 0x7fffef, 0xfffea, 0x3fffe2,
              0x3fffe3, 0x3fffe4, 0x7ffff0, 0x3fffe5, 0x3fffe6, 0x7ffff1, 0x3ffffe0, 0x3ffffe1, 0xfffeb, 0x7fff1,
              0x3fffe7, 0x7ffff2, 0x3fffe8, 0x1ffffec, 0x3ffffe2, 0x3ffffe3, 0x3ffffe4, 0x7ffffde, 0x7ffffdf, 0x3ffffe5,
              0xfffff1, 0x1ffffed, 0x7fff2, 0x1fffe3, 0x3ffffe6, 0x7ffffe0, 0x7ffffe1, 0x3ffffe7, 0x7ffffe2, 0xfffff2,
              0x1fffe4, 0x1fffe5, 0x3ffffe8, 0x3ffffe9, 0xffffffd, 0x7ffffe3, 0x7ffffe4, 0x7ffffe5, 0xfffec, 0xfffff3,
              0xfffed, 0x1fffe6, 0x3fffe9, 0x1fffe7, 0x1fffe8, 0x7ffff3, 0x3fffea, 0x3fffeb, 0x1ffffee, 0x1ffffef,
              0xfffff4, 0xfffff5, 0x3ffffea, 0x7ffff4, 0x3ffffeb, 0x7ffffe6, 0x3ffffec, 0x3ffffed, 0x7ffffe7, 0x7ffffe8,
              0x7ffffe9, 0x7ffffea, 0x7ffffeb, 0xffffffe, 0x7ffffec, 0x7ffffed, 0x7ffffee, 0x7ffffef, 0x7fffff0,
              0x3ffffee };
  
      private static final byte[] CODE_LENGTHS = { 13, 23, 28, 28, 28, 28, 28, 28, 28, 24, 30, 28, 28, 30, 28, 28, 28, 28,
              28, 28, 28, 28, 30, 28, 28, 28, 28, 28, 28, 28, 28, 28, 6, 10, 10, 12, 13, 6, 8, 11, 10, 10, 8, 11, 8, 6, 6,
              6, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 8, 15, 6, 12, 10, 13, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
              7, 7, 7, 7, 7, 7, 8, 7, 8, 13, 19, 13, 14, 6, 15, 5, 6, 5, 6, 5, 6, 6, 6, 5, 7, 7, 6, 6, 6, 5, 6, 7, 6, 5,
              5, 6, 7, 7, 7, 7, 7, 15, 11, 14, 13, 28, 20, 22, 20, 20, 22, 22, 22, 23, 22, 23, 23, 23, 23, 23, 24, 23, 24,
              24, 22, 23, 24, 23, 23, 23, 23, 21, 22, 23, 22, 23, 23, 24, 22, 21, 20, 22, 22, 23, 23, 21, 23, 22, 22, 24,
              21, 22, 23, 23, 21, 21, 22, 21, 23, 22, 23, 23, 20, 22, 22, 22, 23, 22, 22, 23, 26, 26, 20, 19, 22, 23, 22,
              25, 26, 26, 26, 27, 27, 26, 24, 25, 19, 21, 26, 27, 27, 26, 27, 24, 21, 21, 26, 26, 28, 27, 27, 27, 20, 24,
              20, 21, 22, 21, 21, 23, 22, 22, 25, 25, 24, 24, 26, 23, 26, 27, 26, 26, 27, 27, 27, 27, 27, 28, 27, 27, 27,
              27, 27, 26 };
  
      private static final Huffman INSTANCE = new Huffman();
      private final Node root = new Node();
  
      private Huffman() {
          buildTree();
      }
  
      public static Huffman get() {
          return INSTANCE;
      }
  
      void encode(ByteString data, BufferSink sink) throws IOException {
          long current = 0;
          int n = 0;
  
          for (int i = 0; i < data.size(); i++) {
              int b = data.getByte(i) & 0xFF;
              int code = CODES[b];
              int nbits = CODE_LENGTHS[b];
  
              current <<= nbits;
              current |= code;
              n += nbits;
  
              while (n >= 8) {
                  n -= 8;
                  sink.writeByte(((int) (current >> n)));
              }
          }
  
          if (n > 0) {
              current <<= (8 - n);
              current |= (0xFF >>> n);
              sink.writeByte((int) current);
          }
      }
  
      int encodedLength(ByteString bytes) {
          long len = 0;
  
          for (int i = 0; i < bytes.size(); i++) {
              int b = bytes.getByte(i) & 0xFF;
              len += CODE_LENGTHS[b];
          }
  
          return (int) ((len + 7) >> 3);
      }
  
      byte[] decode(byte[] buf) {
          ByteArrayOutputStream baos = new ByteArrayOutputStream();
          Node node = root;
          int current = 0;
          int nbits = 0;
          for (int i = 0; i < buf.length; i++) {
              int b = buf[i] & 0xFF;
              current = (current << 8) | b;
              nbits += 8;
              while (nbits >= 8) {
                  int c = (current >>> (nbits - 8)) & 0xFF;
                  node = node.children[c];
                  if (null == node.children) {
                      // 终端节点
                      baos.write(node.symbol);
                      nbits -= node.terminalBits;
                      node = root;
                  } else {
                      // 非终结符节点
                      nbits -= 8;
                  }
              }
          }
  
          while (nbits > 0) {
              int c = (current << (8 - nbits)) & 0xFF;
              node = node.children[c];
              if (null != node.children || node.terminalBits > nbits) {
                  break;
              }
              baos.write(node.symbol);
              nbits -= node.terminalBits;
              node = root;
          }
  
          return baos.toByteArray();
      }
  
      private void buildTree() {
          for (int i = 0; i < CODE_LENGTHS.length; i++) {
              addCode(i, CODES[i], CODE_LENGTHS[i]);
          }
      }
  
      private void addCode(int sym, int code, byte len) {
          Node terminal = new Node(sym, len);
  
          Node current = root;
          while (len > 8) {
              len -= 8;
              int i = ((code >>> len) & 0xFF);
              if (null == current.children) {
                  throw new IllegalStateException("invalid dictionary: prefix not unique");
              }
              if (null == current.children[i]) {
                  current.children[i] = new Node();
              }
              current = current.children[i];
          }
  
          int shift = 8 - len;
          int start = (code << shift) & 0xFF;
          int end = 1 << shift;
          for (int i = start; i < start + end; i++) {
              current.children[i] = terminal;
          }
      }
  
      private static class Node {
  
          /**
           * 终端节点
           */
          final Node[] children;
  
          /**
           * 终端节点符号
           */
          final int symbol;
  
          /**
           * 终端节点中表示的位数
           */
          final int terminalBits;
  
          Node() {
              this.children = new Node[Normal._256];
              this.symbol = 0;
              this.terminalBits = 0;
          }
  
          /**
           * 构造一个终端节点
           *
           * @param symbol 节点表示
           * @param bits   bits类型的Huffman长度
           */
          Node(int symbol, int bits) {
              this.children = null;
              this.symbol = symbol;
              int b = bits & 0x07;
              this.terminalBits = b == 0 ? 8 : b;
          }
      }
  
  }
  