import { encode as encodeRandom, decode as decodeRandom } from './ascii.random';
import { encode as encodePercent, decode as decodePercent } from './ascii.percent';

// Delta ASCII (Unstable)
// Contextual opportunistic delta encoding

/*
ASCIIコード用デルタエンコーディングアルゴリズム。
非辞書式圧縮文字エンコーディング。
定数計算量の操作のみで構成。
圧縮展開いずれも時間空間ともに線形計算量。
圧縮前よりデータサイズが増加しないことを保証。
肥大化リスクがなく安全かつ高圧縮率であるため普遍的に使用可能。
ASCIIと完全に相互変換可能なため透過的に使用できる。

圧縮文字エンコーディングは転送または保存のために組み込み系などで使用される。
通常の圧縮アルゴリズムでは負荷が高く使用不能または肥大化する数百バイト以下の
文字列のデータサイズを平均20-30%、最大50%削減可能(パーセントエンコーディングは62.5%)。
キャッシュやインメモリKVSの容量を5-10%以上拡大しRPCやIoTのトラフィックを
5-10%以上削減できる可能性がある(個別に専用のエンコーディングを適用すべき場合も多い)。
(NB-)IoTのパケットサイズは数十から数百バイト、最大512バイトのペイロード制限
がある場合もあり圧縮エンコーディングはこのレンジの文字列の圧縮に適合する。
SQL ServerではSCSUが使われている。
Protobufではsintが使われている。

エントロピー符号の最適性の根拠となるシャノンエントロピーは単一のIID空間に対して最適な
符号化を追及するものであることからその最適性は分布に傾向がないゆえに区分する意味のない
単一空間としておよびデータが互いに独立であるゆえに統計的にという非現実的な前提に基づく
何重もの不要な限定条件下での最適性であり最適な符号化を既知のデータに対して算出するのでなく
未知のデータに対して予測する場合に予測との誤差に対してまで最適となるものでもない。
エントロピー符号は符号化空間を2x2、中心の1x1の空間が効率的であるとすると
残部が非効率または非常に非効率となり誤差に対して大きなペナルティを負うが1x1x4のように
空間そのものを分割縮小することで圧縮率の向上とペナルティの軽減が可能である。

*/

/*
比較検討

Delta ASCII:
ASCII互換。
最大50%圧縮(パーセントエンコーディングは62.5%)。
非肥大化保証。
出現頻度の高い2文字を1byteに圧縮できるときのみ圧縮する。
2文字以上の文字列での出現率に基づいて符号化すべきだがデータがないので
1文字での出現率の組み合わせに簡易化(圧縮率はあと5%前後上がるだろう)。
出力も可変長化するなら算術符号化すべきだろう。

ZSCII:
ASCII下位互換。
最大33%圧縮(1/3)？
ASCIIのサブセット(制御文字に制限)。
よくわからないが実装を見ると肥大化しそう。
セグメントIDとオフセットの組または連続のようだがこの方式はあまり
圧縮率が高くなかった。

Packed ASCII:
ASCII下位互換。
最大25%圧縮(1/4)。
ASCIIのサブセット(大文字＋数字＋記号)。

SCSU:
ASCII上位互換。
ASCII文字はUTF-8からは圧縮されない。

HPACK:
ASCII互換。
最大37.5%圧縮。
ハフマン符号の最も優れたASCIIコード用実装と思われるが単語や数値などの
部分文字列の圧縮率はさほど効率的でないと思われる。

ANS/FSE:
単純な直接適用ではあまり圧縮率が上がらないが調整すれば最高圧縮率になる可能性がある。
算術符号は入力の圧縮単位が可変長であることおよび圧縮可能なパターンに制約がないことから
固定長かつ制約付きのDASCIIより理論的には明らかに効率的である。
しかし出力がバイト境界を溢れることで短い入力において非効率となる可能性が高い。
英文中の出現率におけるアルファベット26文字の理論上の最大圧縮率は
最小エントロピー約4.1bitから約48.75%と計算できるがバイト境界を考慮した圧縮率は
2文字以下が0%、3文字が33%、4文字が25%に著しく低下し全体の圧縮率を低下させるため
バイト境界への対応なしに優れた圧縮率は得られないだろう。
さらにオーバーヘッドがハフマン符号より大きいことも短い入力に対する懸念材料となる。
エンコーディングとしては状態の初期化コストも無視できないものとなる懸念がある。
https://arxiv.org/abs/1311.2540
https://github.com/Cyan4973/FiniteStateEntropy
https://www.reddit.com/r/programming/comments/7uoqic/finite_state_entropy_made_easy/?rdt=38141

lz-string:
圧縮アルゴリズム。
ASCII上位互換。
圧縮率が非常に高いように見えるがUTF-16(全文字2バイト以上)としての圧縮率
であるためASCIIやバイナリとしては肥大化しており非効率。
数百文字以上では肥大化する以上に圧縮されるが入力に準じたサイズの辞書を
生成するため入力サイズが大きければ考慮が必要。
数文字程度の短い文字列の圧縮展開でも低速なため集中的な使用には適さない。

*/

/*
v1a 同一文字が3回以上連続することはほとんどないため非効率
[0|0000000]: ASCII
[10|000000]: 7bitの反復回数
[11|000000]: 2bit-1差分x3(0b11は省略)

v1b 同上
[0|0000000]: ASCII
[10|000000]: 7bit repeat count
[11|000000]: 3bit * 2 delta

v2 近接文字が4回連続することは少ないため非効率
[0|0000000]: ASCII
[10|000000]: 2bit * 3 delta
[11|000000]: 3bit * 2 delta

v3a 効率的配置、少ない文字種、ランダム文字列に適している
[0|0000000]: ASCII
[1|0000000]: 3bit + 4bit delta (word: 0.1365; country: 0.1394)
[1|0000000]: 4bit + 3bit delta (word: 0.1420; country: 0.1405)

v3b 初期配置で非ランダム文字列に適している場合がある
[0|0000000]: ASCII
[1|0000000]: 2bit + 5bit delta (word: 0.0700; country: 0.1299)
[1|0000000]: 5bit + 2bit delta (word: 0.1060; country: 0.1034)

v4 配置中央を固定基準とする
[0|0000000]: ASCII
[1|0000000]: 4bit + 3bit delta (word: 0.2086; country: 0.2164)

v5 初期基準を設定
[0|0000000]: ASCII
[1|0000000]: 4bit + 3bit delta (word: 0.3002; country: 0.2245; text: 0.2570)

v6 セグメント遷移規則を詳細化
[0|0000000]: ASCII
[1|0000000]: 4bit + 3bit delta (word: 0.3002; country: 0.2748; text: 0.2600)
[1|0000000]: 4bit + 3bit delta (word: 0.2994; country: 0.2748; text: 0.2600)

v7 セグメント遷移規則を学習
[0|0000000]: ASCII
[1|0000000]: 4bit + 3bit delta (word: 0.2994; country: 0.2749; text: 0.2600)
[1|0000000]: 4bit + 3bit delta (num: 0.4225; hex: 0.1383; word: 0.3305; country: 0.2749; text: 0.2600)

v8 HEX文字列に対応
[0|0000000]: ASCII
[1|0000000]: 4bit + 3bit delta (num: 0.4225; hex: 0.2959; word: 0.3305; country: 0.2749; text: 0.2600)

v9 区切り文字を学習
[0|0000000]: ASCII
[1|0000000]: 4bit + 3bit delta (num: 0.4225; hex: 0.2955; word: 0.3282; country: 0.3047; text: 0.3293)

v10 頻度基準に変更
[0|0000000]: ASCII
[1|0000000]: 4bit + 3bit delta (num: 0.4225; hex: 0.3032; word: 0.3193; country: 0.3052; text: 0.3232)

v11 開始文字を設定
[0|0000000]: ASCII
[1|0000000]: 4bit + 3bit delta (num: 0.4225; hex: 0.3038; word: 0.3239; country: 0.3058; text: 0.3544)
[1|0000000]: 4bit + 3bit delta (num: 0.4224; hex: 0.3041; word: 0.3239; country: 0.3058; text: 0.3544)

v12 ランダム文字列とパーセントエンコーディングに対応
num: 0.4224; hex: 0.3001; 36: 0.2357; 64: 0.2207; pct: 0.5833;
lower: 0.3239; upper: 0.2063; camel: 0.2663; country: 0.3058; text: 0.3544; json: 0.2352;

v13 開始文字を変更
num: 0.4224; hex: 0.2999; 36: 0.2358; 64: 0.2207; pct: 0.5833;
lower: 0.3251; upper: 0.2062; camel: 0.2662; country: 0.3058; text: 0.3534; json: 0.2352;

v14 HEX文字列をランダム文字列に統合
num: 0.4224; hex: 0.4292; 36: 0.2352; 64: 0.2203; pct: 0.5833;
lower: 0.3251; upper: 0.2062; camel: 0.2662; country: 0.3058; text: 0.3534; json: 0.2352;

v15 テーブルを更新
num: 0.4224; hex: 0.4293; 36: 0.2352; 64: 0.2204; pct: 0.5833;
lower: 0.3292; upper: 0.2118; camel: 0.2718; country: 0.3126; text: 0.3785; json: 0.2470;

*/

const ASCII = [...Array(256)].reduce<string>((acc, _, i) => acc + String.fromCharCode(i), '');

const codersN = [
  new Uint8Array(128).fill(~0),
  new Uint8Array('0123456789 .:-,/'.split('').map(c => c.charCodeAt(0))),
  new Uint8Array('0123456789 .:-,/'.split('').map(c => c.charCodeAt(0))),
] as const;
codersN.forEach((dec, i, [enc]) => i && dec.forEach((code, i) => enc[code] = i));
const codersH = [
  new Uint8Array(128).fill(~0),
  new Uint8Array('0123456789ABCDEF'.split('').map(c => c.charCodeAt(0))),
  new Uint8Array('0123456789abcdef'.split('').map(c => c.charCodeAt(0))),
] as const;
codersH.forEach((dec, i, [enc]) => i && dec.forEach((code, i) => enc[code] = i));
const codersF = [
  new Uint8Array(128).fill(~0),
  new Uint8Array('TAOSWIHCBFMPERDL'.split('').map(c => c.charCodeAt(0))),
  new Uint8Array('taoswihcbfmperdl'.split('').map(c => c.charCodeAt(0))),
] as const;
codersF.forEach((dec, i, [enc]) => i && dec.forEach((code, i) => enc[code] = i));
const codersL = [
  new Uint8Array(128).fill(~0),
  new Uint8Array('TNSHRDLC EAOIUYG'.split('').map(c => c.charCodeAt(0))).reverse(),
  new Uint8Array('tnshrdlc eaoiuyg'.split('').map(c => c.charCodeAt(0))).reverse(),
] as const;
codersL.forEach((dec, i, [enc]) => i && dec.forEach((code, i) => enc[code] = i));
const codersR = [
  new Uint8Array(128).fill(~0),
  new Uint8Array('TNSHRDL CEAOIUYG'.split('').map(c => c.charCodeAt(0))),
  new Uint8Array('tnshrdl ceaoiuyg'.split('').map(c => c.charCodeAt(0))),
] as const;
codersR.forEach((dec, i, [enc]) => i && dec.forEach((code, i) => enc[code] = i));
assert(codersL[0][7] === codersR[0][7]);
const table = [
  codersN,
  codersF,
  codersL,
  codersR,
] as const;
const Table = {
  N: table.indexOf(codersN),
  F: table.indexOf(codersF),
  L: table.indexOf(codersL),
  R: table.indexOf(codersR),
} as const;
const layout = 'ZQJKXFYPAOEUIDHTNSLRCGBMWV';
const frequency = new Uint8Array([
  ...new Uint8Array(32).map(() => Table.F),
  ...new Uint8Array(16).map(() => Table.F),
  ...'0123456789'.split('').map(() => Table.N),
  ...`:;<=>?@`.split('').map(() => Table.F),
  ...'ABCDEFGHIJKLMNOPQRSTUVWXYZ'.split('').map(c => layout.indexOf(c) < 13 ? Table.R : Table.L),
  ...'[\\]^_`'.split('').map(() => Table.F),
  ...'ABCDEFGHIJKLMNOPQRSTUVWXYZ'.split('').map(c => layout.indexOf(c) < 13 ? Table.R : Table.L),
  ...'{|}~\x7f'.split('').map(() => Table.F),
]);
const axisU = 'A'.charCodeAt(0);
const axisL = 'a'.charCodeAt(0);
const axisN = '0'.charCodeAt(0);
const axisH = 0;
const axisB = axisL;
const enum Segment {
  Upper = 0,
  Lower = 1,
  Number = 2,
  Other = 3,
}
function segment(code: number): Segment {
  if (code < 0x61) {
    if (code < 0x3a) {
      if (code < 0x30) return Segment.Other;
      return Segment.Number;
    }
    if (code < 0x5b) {
      if (code < 0x41) return Segment.Other;
      return Segment.Upper;
    }
    return Segment.Other;
  }
  else {
    if (code < 0x7b) return Segment.Lower;
    return Segment.Other;
  }
}
let randstate = false;
function align(code: number, base: number, axis: number): number {
  randstate = false;
  switch (segment(code)) {
    case Segment.Upper:
      hexstate = isHEX(code);
      if (hexstate >>> 4 !== 0) return axisH;
      switch (segment(base)) {
        // ABBR
        case Segment.Upper:
          incFreq(Segment.Upper);
          return axisU;
        // CamelCase
        case Segment.Lower:
          return axisL;
        // 0FF7
        case Segment.Number:
          randstate = true;
          return axisU;
        // ^Case
        // _Case
        case Segment.Other:
          return freq >>> 2 > (freq & 0b11)
            ? axisU
            : axisL;
      }
    case Segment.Lower:
      hexstate = isHEX(code);
      if (hexstate >>> 4 !== 0) return axisH;
      switch (segment(base)) {
        case Segment.Upper:
          incFreq(Segment.Lower);
          return axisL;
        case Segment.Lower:
          return axisL;
        case Segment.Number:
          randstate = true;
          return axisL;
        case Segment.Other:
          return axisL;
      }
    case Segment.Number:
      hexstate = isHEX(code);
      if (hexstate >>> 4 !== 0) return axisH;
      switch (segment(base)) {
        case Segment.Upper:
          return axisN;
        case Segment.Lower:
          return axisN;
        case Segment.Number:
          return axisN;
        case Segment.Other:
          return axisN;
      }
    case Segment.Other:
      hexstate = hexstate >>> 4 !== 0 && (code === 0x2d || code === 0x3a) ? hexstate : 0;
      if (hexstate >>> 4 !== 0) return axisH;
      switch (segment(base)) {
        // J.Doe
        case Segment.Upper:
          return axisU;
        // z and
        case Segment.Lower:
          return axisL;
        // 0.0
        case Segment.Number:
          return axisN;
        // , and
        case Segment.Other:
          return axis || axisB;
      }
  }
}
let freq = 0;
function incFreq(segment: Segment.Upper | Segment.Lower): void {
  const maskU = 0b1100;
  const maskL = 0b0011;
  if (segment === Segment.Upper) {
    if ((freq & maskU) === maskU) {
      freq = freq >>> 1 & 0b0101;
    }
    freq += 0b0100;
  }
  else {
    if ((freq & maskL) === maskL) {
      freq = freq >>> 1 & 0b0101;
    }
    freq += 0b0001;
  }
}
let hexstate = 0;
function isHEX(code: number): number {
  assert(hexstate >>> 8 === 0);
  if (code < 0x30) return 0;
  if (code < 0x3a) {
    return hexstate === 0b111
        || hexstate >>> 4 !== 0
      ? 0b111 | hexstate & hexstate << 4
      : 0b111 | hexstate << 4;
  }
  if (code < 0x41) return 0;
  if (code < 0x47) {
    return hexstate === 0b111
        || (hexstate >>> 4 & hexstate) === 0b011
      ? 0b011 | 0b111 << 4
      : 0b011;
  }
  if (code < 0x61) return 0;
  if (code < 0x67) {
    return hexstate === 0b111
        || (hexstate >>> 4 & hexstate) === 0b101
      ? 0b101 | 0b111 << 4
      : 0b101;
  }
  return 0;
}
const seps = Uint8Array.from(Array(128), (_, i) =>
  ' .:-,/\t"_'.includes(String.fromCharCode(i)) ? i : 0);
let sep = 0;
function encCode(code: number, base: number, axis: number): number {
  let delta = 1 << 7;
  switch (axis) {
    case axisU:
    case axisL: {
      const coders = table[frequency[base]];
      if (code === sep) switch (coders) {
        case codersL:
        case codersR:
          return 7;
      }
      if (code < axis || axis + 26 - 1 < code) break;
      delta = coders[0][code];
      break;
    }
    case axisN: {
      const coders = table[frequency[axis <= base && base < axis + 10 ? base : axis]];
      if (code < axis && axis + 10 - 1 < code) break;
      delta = coders[0][code];
      break;
    }
  }
  sep = seps[code] || sep;
  return delta;
}
function decDelta(delta: number, base: number, axis: number): number {
  let code: number;
  switch (axis) {
    case axisU:
    case axisL: {
      const coders = table[frequency[base]];
      if (delta === 7) switch (coders) {
        case codersL:
        case codersR:
          return sep;
      }
      code = coders[axis === axisU ? 1 : 2][delta];
      break;
    }
    case axisN: {
      const coders = table[frequency[axis <= base && base < axis + 10 ? base : axis]];
      code = coders[1][delta];
      break;
    }
    default:
      throw 0;
  }
  sep = seps[code] || sep;
  return code;
}
function reset(): void {
  axis = axisB;
  hexstate = 0;
  randstate = false;
}
function clear(): void {
  reset();
  freq = 0;
  sep = 0x20;
  hopts.skip = 0;
}

const popts = {
  start: 0,
  next: 0,
};

const hopts = {
  start: 0,
  next: 0,
  skip: 0,
};

let axis = 0;

export function encode(input: string, huffman = true): string {
  clear();
  let output = '';
  let base = sep;
  let buffer = 0;
  for (let i = 0, j = 0; i < input.length; ++i) {
    const code = input.charCodeAt(i);
    assert(code >>> 8 === 0);
    if (j === 0) {
      if (i + 1 === input.length) {
        output += ASCII[code];
        break;
      }
      if (code === 0x25) {
        popts.start = i;
        output += '%' + encodePercent(input, codersH[0], popts);
        i = popts.next === i ? i + 1 : popts.next;
        output += input[i] ?? '';
        axis = align(code, base, axis);
        base = input.charCodeAt(i);
        continue;
      }
      const hex = axis === axisH && isHEX(code) >>> 4 !== 0;
      if (huffman && (randstate || hex) && i >= hopts.skip) {
        hopts.start = hopts.skip = i;
        output += encodeRandom(input, hex ? hexstate >>> 4 & hexstate : 0, hopts);
        i = hopts.next - 1;
        if (hopts.next === hopts.start) {
          // 同じ位置で異なる圧縮エンコードへリトライするとデコード不能になるためリトライさせない。
          assert(hex && !randstate || randstate && !hex);
          if (hex) {
            axis = axisB;
          }
          else {
            randstate = false;
          }
        }
        else {
          base = input.charCodeAt(i);
          reset();
        }
        continue;
      }
      const delta = hex
        ? codersH[0][code]
        : encCode(code, base, axis);
      if (delta >>> 4 || axis === axisH && !hex || i < hopts.skip) {
        output += ASCII[code];
      }
      else {
        buffer = delta << 3;
        ++j;
      }
    }
    else {
      const sep$ = sep;
      const hex = axis === axisH && isHEX(code) >>> 4 !== 0;
      const delta = hex
        ? codersH[0][code]
        : encCode(code, base, axis);
      if (delta >>> 3 || axis === axisH && !hex) {
        if (!hex) {
          sep = sep$;
        }
        output += ASCII[base];
        buffer = 0;
        i -= j;
        j = 0;
        continue;
      }
      else {
        buffer |= delta;
        assert(buffer >>> 8 === 0);
        output += ASCII[0b1 << 7 | buffer];
      }
      buffer = 0;
      j = 0;
    }
    axis = align(code, base, axis);
    base = code;
  }
  assert(buffer === 0);
  assert(output.length <= input.length);
  return output;
}

export function decode(input: string, huffman = true): string {
  clear();
  let output = '';
  let base = sep;
  let hexcase = 1;
  for (let i = 0; i < input.length; ++i) {
    let code = input.charCodeAt(i);
    assert(code >>> 8 === 0);
    const hex = axis === axisH;
    if (code === 0x25) {
      popts.start = ++i;
      output += decodePercent(input, codersH[1], popts) || '%';
      i = popts.next;
      output += input[i] ?? '';
      axis = align(code, base, axis);
      base = input.charCodeAt(i);
      continue;
    }
    else if (code <= 0x7f) {
      output += ASCII[code];
      sep = seps[code] || sep;
    }
    else if (huffman && (randstate || hex)) {
      hopts.start = i;
      output += decodeRandom(input, hex ? hexstate >>> 4 & hexstate : 0, hopts);
      i = hopts.next - 1;
      if (hopts.next === hopts.start) {
        if (hex) {
          axis = axisB;
        }
        else {
          randstate = false;
        }
      }
      else {
        base = output.charCodeAt(output.length - 1);
        reset();
      }
      continue;
    }
    else {
      const delta = code;
      code = axis === axisH
        ? codersH[hexcase][delta >>> 3 & 0b1111]
        : decDelta(delta >>> 3 & 0b1111, base, axis);
      output += ASCII[code];
      axis = align(code, base, axis);
      base = code;
      hexcase = segment(code) <= Segment.Lower ? segment(code) + 1 : hexcase;
      code = axis === axisH
        ? codersH[hexcase][delta & 0b111]
        : decDelta(delta & 0b0111, base, axis);
      output += ASCII[code];
    }
    axis = align(code, base, axis);
    base = code;
    hexcase = segment(code) <= Segment.Lower ? segment(code) + 1 : hexcase;
  }
  return output;
}