# 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))    # X, Y 방향 픽셀 밀도
    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])
    # 네 가지 스캔 방향 정의
    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
    # 끝에 두 개의 0을 종료 마커로 추가
    if(AClist[-1] == 0):
        re.extend([0, 0])
    return np.array(re, np.int16)

             값               비트 길이            실제 저장 값
              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                  ...

# 특수 바이너리 인코딩 형식
# 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: 파일에 기록되지 않은 바이너리 데이터
# 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")
            exit()
    else:                            # AC
        if((n > 15) or (bit > 11) or (((n != 0) and (n != 15)) and (bit == 0))):
            print("Write AC data Error")
            exit()
        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: 인코딩의 바이너리 비트 수
# str_code: 인코딩의 바이너리 데이터
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!")
        exit()
    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)