# JPEG形式のデコーディング情報を書き込む
# filename: 出力ファイル名
# h: 画像の高さ
# w: 画像の幅
def write_head(filename, h, w):
    # バイナリ書き込みモードでファイルを開く（上書き）
    fp = open(filename, "wb")

    # SOI
    fp.write(pack(">H", 0xffd8))
    # APP0
    fp.write(pack(">H", 0xffe0))
    fp.write(pack(">H", 16))            # APP0のバイト数
    fp.write(pack(">L", 0x4a464946))    # JFIF
    fp.write(pack(">B", 0))            # 0
    fp.write(pack(">H", 0x0101))        # バージョン番号: 1.1
    fp.write(pack(">B", 0x01))            # ピクセル密度単位: ピクセル/インチ
    fp.write(pack(">L", 0x00480048))    # XY方向のピクセル密度
    fp.write(pack(">H", 0x0000))        # サムネイル情報なし
    # DQT_0
    fp.write(pack(">H", 0xffdb))
    fp.write(pack(">H", 64+3))        # 量子化表のバイト数
    fp.write(pack(">B", 0x00))            # 量子化表精度: 8bit(0)  量子化表ID: 0
    tbl = block2zz(std_luminance_quant_tbl)
    for item in tbl:
        fp.write(pack(">B", item))    # 量子化表0の内容
    # DQT_1
    fp.write(pack(">H", 0xffdb))
    fp.write(pack(">H", 64+3))        # 量子化表のバイト数
    fp.write(pack(">B", 0x01))            # 量子化表精度: 8bit(0)  量子化表ID: 1
    tbl = block2zz(std_chrominance_quant_tbl)
    for item in tbl:
        fp.write(pack(">B", item))    # 量子化表1の内容
    # SOF0
    fp.write(pack(">H", 0xffc0))
    fp.write(pack(">H", 17))            # フレーム画像情報のバイト数
    fp.write(pack(">B", 8))                # 精度: 8bit
    fp.write(pack(">H", h))                # 画像の高さ
    fp.write(pack(">H", w))                # 画像の幅
    fp.write(pack(">B", 3))                # 色成分数: 3(YCrCb)
    fp.write(pack(">B", 1))                # 色成分ID: 1
    fp.write(pack(">H", 0x1100))        # 水平垂直サンプリング因子: 1  使用する量子化表ID: 0
    fp.write(pack(">B", 2))                # 色成分ID: 2
    fp.write(pack(">H", 0x1101))        # 水平垂直サンプリング因子: 1  使用する量子化表ID: 1
    fp.write(pack(">B", 3))                # 色成分ID: 3
    fp.write(pack(">H", 0x1101))        # 水平垂直サンプリング因子: 1  使用する量子化表ID: 1
    # DHT_DC0
    fp.write(pack(">H", 0xffc4))
    fp.write(pack(">H", len(std_huffman_DC0)+3))    # ハフマン表のバイト数
    fp.write(pack(">B", 0x00))                # DC0
    for item in std_huffman_DC0:
        fp.write(pack(">B", item))            # ハフマン表の内容
    # DHT_AC0
    fp.write(pack(">H", 0xffc4))
    fp.write(pack(">H", len(std_huffman_AC0)+3))    # ハフマン表のバイト数
    fp.write(pack(">B", 0x10))                # AC0
    for item in std_huffman_AC0:
        fp.write(pack(">B", item))            # ハフマン表の内容
    # DHT_DC1
    fp.write(pack(">H", 0xffc4))
    fp.write(pack(">H", len(std_huffman_DC1)+3))    # ハフマン表のバイト数
    fp.write(pack(">B", 0x01))                # DC1
    for item in std_huffman_DC1:
        fp.write(pack(">B", item))            # ハフマン表の内容
    # DHT_AC1
    fp.write(pack(">H", 0xffc4))
    fp.write(pack(">H", len(std_huffman_AC1)+3))    # ハフマン表のバイト数
    fp.write(pack(">B", 0x11))                # AC1
    for item in std_huffman_AC1:
        fp.write(pack(">B", item))            # ハフマン表の内容
    # SOS
    fp.write(pack(">H", 0xffda))
    fp.write(pack(">H", 12))                # スキャン開始情報のバイト数
    fp.write(pack(">B", 3))                # 色成分数: 3
    fp.write(pack(">H", 0x0100))        # 色成分1のDC、ACに使用するハフマン表ID
    fp.write(pack(">H", 0x0211))        # 色成分2のDC、ACに使用するハフマン表ID
    fp.write(pack(">H", 0x0311))        # 色成分3のDC、ACに使用するハフマン表ID
    fp.write(pack(">B", 0x00))
    fp.write(pack(">B", 0x3f))
    fp.write(pack(">B", 0x00))                # 固定値
    fp.close()

# 画像サイズを変換し、8×8のブロックに分割可能にする
if((h % 8 == 0) and (w % 8 == 0)):
    nblock = int(h * w / 64)
else:
    h = h // 8 * 8
    w = w // 8 * 8
    YCrCb = cv2.resize(YCrCb, [h, w], cv2.INTER_CUBIC)
    nblock = int(h * w / 64)

YCrCb = cv2.cvtColor(BGR, cv2.COLOR_BGR2YCrCb)
npdata = np.array(YCrCb, np.int16)

for i in range(0, h, 8):
    for j in range(0, w, 8):
        ...

now_block = npdata[i:i+8, j:j+8, 0] - 128        # 8×8ブロックを取り出し、128を引く（Y成分）
now_block = npdata[i:i+8, j:j+8, 2] - 128        # 8×8ブロックを取り出し、128を引く（Cb成分）
now_block = npdata[i:i+8, j:j+8, 1] - 128        # 8×8ブロックを取り出し、128を引く（Cr成分）
now_block_dct = cv2.dct(np.float32(now_block))    # DCT変換

# 明度量子化表
std_luminance_quant_tbl = np.array(
    [
        [16, 11, 10, 16, 24, 40, 51, 61],
        [12, 12, 14, 19, 26, 58, 60, 55],
        [14, 13, 16, 24, 40, 57, 69, 56],
        [14, 17, 22, 29, 51, 87, 80, 62],
        [18, 22, 37, 56, 68,109,103, 77],
        [24, 35, 55, 64, 81,104,113, 92],
        [49, 64, 78, 87,103,121,120,101],
        [72, 92, 95, 98,112,100,103, 99]
    ],
    np.uint8
)
# 色度量子化表
std_chrominance_quant_tbl = np.array(
    [
        [17, 18, 24, 47, 99, 99, 99, 99],
        [18, 21, 26, 66, 99, 99, 99, 99],
        [24, 26, 56, 99, 99, 99, 99, 99],
        [47, 66, 99, 99, 99, 99, 99, 99],
        [99, 99, 99, 99, 99, 99, 99, 99],
        [99, 99, 99, 99, 99, 99, 99, 99],
        [99, 99, 99, 99, 99, 99, 99, 99],
        [99, 99, 99, 99, 99, 99, 99, 99]
    ],
    np.uint8
)

now_block_qut = quantize(now_block_dct, 0)        # Y成分 量子化
now_block_qut = quantize(now_block_dct, 2)        # Cb成分 量子化
now_block_qut = quantize(now_block_dct, 1)        # Cr成分 量子化

# 量子化
# block: 現在の8×8ブロックのデータ
# dim: 次元  0:Y  1:Cr  2:Cb
def quantize(block, dim):
    if(dim == 0):
        # 明度量子化表を使用
        qarr = std_luminance_quant_tbl
    else:
        # 色度量子化表を使用
        qarr = std_chrominance_quant_tbl
    return (block / qarr).round().astype(np.int16)

now_block_zz = block2zz(now_block_qut)        # zigzagスキャン

# zigzagスキャン
# block: 現在の8×8ブロックのデータ
def block2zz(block):
    re = np.empty(64, np.int16)
    # 現在のblock内の位置
    pos = np.array([0, 0])
    # 4つのスキャン方向を定義
    R = np.array([0, 1])
    LD = np.array([1, -1])
    D = np.array([1, 0])
    RU = np.array([-1, 1])
    for i in range(0, 64):
        re[i] = block[pos[0], pos[1]]
        if(((pos[0] == 0) or (pos[0] == 7)) and (pos[1] % 2 == 0)):
            pos = pos + R
        elif(((pos[1] == 0) or (pos[1] == 7)) and (pos[0] % 2 == 1)):
            pos = pos + D
        elif((pos[0] + pos[1]) % 2 == 0):
            pos = pos + RU
        else:
            pos = pos + LD
    return re

last_block_ydc = 0
last_block_cbdc = 0
last_block_crdc = 0

now_block_dc = now_block_zz[0] - last_block_ydc # 直流成分を差分形式で記録
last_block_ydc = now_block_zz[0] # 今回の値を記録

now_block_dc = now_block_zz[0] - last_block_cbdc
last_block_cbdc = now_block_zz[0]

now_block_dc = now_block_zz[0] - last_block_crdc
last_block_crdc = now_block_zz[0]

now_block_ac = RLE(now_block_zz[1:])

# 0のランレングス符号化
# AClist: 符号化する交流データ
def RLE(AClist: np.ndarray) -> np.ndarray:
    re = []
    cnt = 0
    for i in range(0, 63):
        if(AClist[i] == 0 and cnt != 15):
            cnt += 1
        else:
            re.append(cnt)
            re.append(AClist[i])
            cnt = 0
    # 末尾の[15 0]を削除
    while(re[-1] == 0):
        re.pop()
        re.pop()
        if(len(re) == 0):
            break
    # 終端に2つの0を追加
    if(AClist[-1] == 0):
        re.extend([0, 0])
    return np.array(re, np.int16)

             数値               bit長さ            実際の保存値
              0                   0                   無し
            -1,1                  1                  0,1
         -3,-2,2,3                2              00,01,10,11
   -7,-6,-5,-4,4,5,6,7            3    000,001,010,011,100,101,110,111
     -15,..,-8,8,..,15            4       0000,..,0111,1000,..,1111
    -31,..,-16,16,..,31           5     00000,..,01111,10000,..,11111
    -63,..,-32,32,..,63           6                  ...
   -127,..,-64,64,..,127          7                  ...
  -255,..,-128,128,..,255         8                  ...
  -511,..,-256,256,..,511         9                  ...
 -1023,..,-512,512,..,1023       10                  ...
-2047,..,-1024,1024,..,2047      11                  ...

# 特殊な2進符号化形式
# num: 符号化する数字
def tobin(num):
    s = ""
    if(num > 0):
        while(num != 0):
            s += '0' if(num % 2 == 0) else '1'
            num = int(num / 2)
        s = s[::-1]    # 反転
    elif(num < 0):
        num = -num
        while(num != 0):
            s += '1' if(num % 2 == 0) else '0'
            num = int(num / 2)
        s = s[::-1]
    return s

s = write_num(s, -1, now_block_dc, DC0)        # 符号化方式に従って直流データを書き込む
for l in range(0, len(now_block_ac), 2):         # 交流データを書き込む
    s = write_num(s, now_block_ac[l], now_block_ac[l+1], AC0)
    while(len(s) >= 8):                     # データが長すぎるとメモリオーバーになる
        num = int(s[0:8], 2)                 # 実行速度が遅くなる
        fp.write(pack(">B", num))
        if(num == 0xff):                 # マークとの衝突を防ぐ
            fp.write(pack(">B", 0))             # データ中に0xffが現れた場合は後ろに0x00を追加
        s = s[8:len(s)]

# 符号化方式に従ってデータを書き込む
# s: ファイルに書き込まれていない2進データ
# n: データの先頭の0の個数（-1はDC）
# num: 書き込むデータ
# tbl: ノーマルハフマン符号化辞書
def write_num(s, n, num, tbl):
    bit = 0
    tnum = num
    while(tnum != 0):
        bit += 1
        tnum = int(tnum / 2)
    if(n == -1):                 # DC
        tnum = bit
        if(tnum > 11):
            print("Write DC data Error")
            xit()
    else:                     # AC
        if((n > 15) or (bit > 11) or (((n != 0) and (n != 15)) and (bit == 0))):
            print("Write AC data Error")
            xit()
        tnum = n * 10 + bit + (0 if(n != 15) else 1)
    # ノーマルハフマン符号化で0の個数（AC）およびnumのビット長を記録
    s += tbl[tnum].str_code
    # 特殊形式のデータとしてnumを保存
    s += tobin(num)
    return s

# 明度直流成分のノーマルハフマン符号化表
std_huffman_DC0 = np.array(
    [0, 0, 7, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
     4, 5, 3, 2, 6, 1, 0, 7, 8, 9, 10, 11],
    np.uint8
)
...
# ハフマン辞書に変換
DC0 = DHT2tbl(std_huffman_DC0)    # 明度直流成分
DC1 = DHT2tbl(std_huffman_DC1)    # 色度直流成分
AC0 = DHT2tbl(std_huffman_AC0)    # 明度交流成分
AC1 = DHT2tbl(std_huffman_AC1)    # 色度交流成分

# ハフマン辞書を記録するクラス
# symbol: 原始データ
# code: 対応する符号化データ
# n_bit: 符号化の2進ビット数
# str_code: 符号化の2進データ
class Sym_Code():
    def __init__(self, symbol, code, n_bit):
        self.symbol = symbol
        self.code = code
        str_code=''
        mask = 1 << (n_bit - 1)
        for i in range(0, n_bit):
            if(mask & code):
                str_code += '1'
            else:
                str_code += '0'
            mask >>= 1
        self.str_code = str_code
    """出力形式を定義"""
    def __str__(self):
        return "0x{:0>2x}    |  {}".format(self.symbol, self.str_code)
    """ソート基準を定義"""
    def __eq__(self, other):
        return self.symbol == other.symbol
    def __le__(self, other):
        return self.symbol < other.symbol
    def __gt__(self, other):
        return self.symbol > other.symbol


# ノーマルハフマン符号化表をハフマン辞書に変換
# data: 定義されたノーマルハフマン符号化表
def DHT2tbl(data):
    numbers = data[0:16]             # 1～16ビット長の符号化に対応する個数
    symbols = data[16:len(data)]     # 原始データ
    if(sum(numbers) != len(symbols)):     # 正しいノーマルハフマン符号化表か判定
        print("Wrong DHT!")
        xit()
    code = 0
    SC = []                     # 辞書のリストを記録
    for n_bit in range(1, 17):
        # ノーマルハフマン符号化ルールに従って辞書を換算
        for symbol in symbols[sum(numbers[0:n_bit-1]):sum(numbers[0:n_bit])]:
            SC.append(Sym_Code(symbol, code, n_bit))
            code += 1
        code <<= 1
    return sorted(SC)