int curPos = 16, curCode = 0;
for (int i = 0; i < 16; i++) {
    int count = temp[i];//count為二進(jìn)制位數(shù)為i+1的個(gè)數(shù)
    curCode <<= 1;		//curCode為當(dāng)前huffman編碼數(shù)值
    while (count--) {	//一次循環(huán)生成一個(gè)
        uint16_t code=curCode;
        uint8_t bit=i+1;//比特位有幾位 00為2位
        uint8_t weight=temp[curPos];//權(quán)重是按照順序排列的，如比特位為兩位的編碼有兩個(gè)，設(shè)為00，01，后面權(quán)重排列為1，2，則00對(duì)應(yīng)1，01對(duì)應(yīng)2
        pair<uint8_t, uint8_t> t1(bit,weight);
        //<code,<bit,weight>
        pair<uint16_t, pair<uint8_t, uint8_t>> t2(curCode,t1);
        table.insert(t2);
        curCode++;
        curPos++;
    }
}

curValue = (curValue >= pow(2, curValueLength - 1) ? curValue : curValue - pow(2, curValueLength) + 1);

double** UnZigZag(int* originArray){
    double** table=new double*[ROW];
    for(int i=0;i<ROW;i++) table[i]=new double[COL];
    int cur=0,x=0,y=0;
    bool flag = true;//true是右上 false是左下
    while (cur < 64) {
        table[y][x] = originArray[cur++];
        if (flag) { x++; y--; }
        else { x--; y++; }
        if (x < 0 || y < 0 || x>7 || y>7) flag = !flag;
        if (x < 0 && y>7) { x = 1; y = 7; }
        if (x < 0) x = 0;
        else if (x > 7) { x = 7; y += 2; }
        if (y < 0) y = 0;
        else if (y > 7) { y = 7; x += 2; }
    }
    return table;

double** JPEGData::createDCTAndIDCTArray(int row){
    double** res=new double*[row];
    for(int i=0;i<row;i++) res[i]=new double[row];
    // cout<<endl;
    for(int i=0;i<row;i++){
        for(int j=0;j<row;j++){
            double t=0;
            if(i==0) t=sqrt(1.0/row);
            else t=sqrt(2.0/row);
            res[i][j]=t*cos(M_PI*(j+0.5)*i/row);
            // cout<<res[i][j]<<" ";
        }
        // cout<<endl;
    }
    return res;
}
//設(shè)返回的矩陣為A
//DCT原理 Y=A*X*A'(X為正變換輸入，Y是輸出)
//IDCT原理X=A'*Y*A（Y是逆變換輸入，X是輸出'是轉(zhuǎn)置）
void JPEGData::IDCT(double** originMatrix){
    vector<vector<double>> temp(ROW,vector<double>(COL,0));
    for(int i=0;i<ROW;i++){
        for(int j=0;j<COL;j++){
            double sum=0;
            for(int k=0;k<COL;k++){
                sum+=DCTAndIDCTArray[k][i]*originMatrix[k][j];
            }
            temp[i][j]=sum;
        }
    }
    for(int i=0;i<ROW;i++){
        for(int j=0;j<COL;j++){
            double sum=0;
            for(int k=0;k<COL;k++){
                sum+=temp[i][k]*DCTAndIDCTArray[k][j];
            }
            originMatrix[i][j]=sum;
        }
    }
}
void JPEGData::DCT(double** originMatrix){
    vector<vector<double>> temp(ROW,vector<double>(COL,0));
    for(int i=0;i<ROW;i++){
        for(int j=0;j<COL;j++){
            double sum=0;
            for(int k=0;k<COL;k++){
                sum+=DCTAndIDCTArray[i][k]*originMatrix[k][j];
            }
            temp[i][j]=sum;
        }
    }
    for(int i=0;i<ROW;i++){
        for(int j=0;j<COL;j++){
            double sum=0;
            for(int k=0;k<COL;k++){
                sum+=temp[i][k]*DCTAndIDCTArray[j][k];
            }
            originMatrix[i][j]=sum;
        }
    }
}

struct RGB{
	uint8_t red;
	uint8_t green;
	uint8_t blue;
};
RGB** JPEGData::YCbCrToRGB(const int* YUV){
    RGB **res = new RGB *[ROW * max_v_samp_factor];
    int matrixCount = YUV[0] + YUV[1] + YUV[2];
    int crCount = 0, cbCount = 0;
    //1＝Y(jié), 2＝Cb, 3＝Cr
    //式子 scale*x,scale*y
    double cb_h_samp_scale=component[1].h_samp_factor*1.0/max_h_samp_factor,
           cb_v_samp_scale=component[1].v_samp_factor*1.0/max_v_samp_factor,
           cr_h_samp_scale=component[2].h_samp_factor*1.0/max_h_samp_factor,
           cr_v_samp_scale=component[2].v_samp_factor*1.0/max_v_samp_factor;
    for (int i = 0; i < ROW * max_v_samp_factor; i++)
        res[i] = new RGB[COL * max_h_samp_factor];
    //此處直接生成rgb值
    //注意，此處YCbCr的對(duì)應(yīng)關(guān)系與采樣因子有關(guān)
    //這個(gè)ycbcr存的是一個(gè)MCU，假設(shè)YUV為411，那么ycbcr有6個(gè)
    //這種方式轉(zhuǎn)換不了YUV為420的，因?yàn)閿?shù)組越界了，不過(guò)可以加個(gè)判斷，我懶得改了
    // cout<<endl;
    for(int j=0;j<ROW * max_v_samp_factor;j++){
        for(int k=0;k<COL * max_h_samp_factor;k++){
            int yPos = (j / ROW) * component[0].h_samp_factor + (k / COL);
            int cbPos = YUV[0] + (int)((k / ROW) * cb_v_samp_scale) + (int)((j / COL) * cb_h_samp_scale);
            int crPos = YUV[0] + YUV[1] + (int)((k / ROW) * cr_v_samp_scale) + (int)((j / COL) * cr_h_samp_scale);
            double y = ycbcr[yPos][j % ROW][k % COL];
            double cb = ycbcr[cbPos][(int)(j * cb_v_samp_scale)][(int)(k * cb_h_samp_scale)];
            double cr = ycbcr[crPos][(int)(j * cr_v_samp_scale)][(int)(k * cr_h_samp_scale)];
            res[j][k].red   =RGBValueLimit(128+y+1.402  *cr);
            res[j][k].green =RGBValueLimit(128+y-0.71414*cr-0.34414*cb);
            res[j][k].blue  =RGBValueLimit(128+y+1.772  *cb);
            // 輸出當(dāng)前選擇的矩陣
            //cout<<dec<<yPos<<" "<<cbPos<<" "<<crPos<<" ";
            // cout<<hex<<setw(2)<<setfill('0')<<(int)res[j][k].red
            //          <<setw(2)<<setfill('0')<<(int)res[j][k].green
            //          <<setw(2)<<setfill('0')<<(int)res[j][k].blue<<" ";
        }
        // cout<<endl;
    }
    // cout<<endl;
    return res;
}

#pragma once
#define _USE_MATH_DEFINES
#include <cmath>
#include <fstream>
#include <stdint.h>
#include <utility>
#ifndef _IMAGE_
#define _IMAGE_
#include "Util.h"
#include <string>
#include <vector>
#include <iostream>
using namespace std;
NAME_SPACE_START(myUtil)
#define ROW 8
#define COL 8
#define HUFFMAN_DECODE_DEQUE_CACHE 64//單位：位
// #define _DEBUG_
// #define _DEBUGOUT_
#define FREE_VECTOR_LP(vectorName) \
    for(auto item : vectorName){	\
		for(int i=0;i<ROW;i++)\
			delete [] item[i];\
        delete [] item;	\
    }\
	vectorName.clear();
//釋放二維指針
#define FREE_LP_2(lpName,row) \
	for(int i=0;i<row;i++){\
		delete [] lpName[i];\
	}\
	delete [] lpName;
//段類(lèi)型
enum JPEGPType{
    SOF0    = 0xC0,     //幀開(kāi)始
    SOF1    = 0xC1,     //幀開(kāi)始
    SOF2    = 0xC2,     //幀開(kāi)始
    DHT     = 0xC4,     //哈夫曼表
    SOI     = 0xD8,     //文件頭
    EOI     = 0xD9,     //文件尾
    SOS     = 0xDA,     //掃描行開(kāi)始
    DQT     = 0xDB,     //定義量化表
    DRI     = 0xDD,     //定義重新開(kāi)始間隔
    APP0    = 0xE0,     //定義交換格式和圖像識(shí)別信息
    APP1    = 0xE1,     //定義交換格式和圖像識(shí)別信息
    APP2    = 0xE2,     //定義交換格式和圖像識(shí)別信息
    COM     = 0xFE      //注釋
};
//將一維數(shù)組變?yōu)槎S數(shù)組
double** UnZigZag(int* originArray);
struct RGB{
	uint8_t red;
	uint8_t green;
	uint8_t blue;
};
//SOS
class JPEGScan{
public:
	//componentId,<DC,AC>
	map<uint8_t,pair<uint8_t,uint8_t>> componentHuffmanMap;
	bool Init(fstream& file,uint16_t len);
};
//APP
class JPEGInfo{
public:
	uint16_t version;
};
//DHT
class JPEGHuffmanCode{
public:
	using iterator = map<uint16_t,pair<uint8_t,uint8_t>>::iterator;
	//<code,<bit,weight>
	map<uint16_t,pair<uint8_t,uint8_t>> table;
	//init huffman table
	bool Init(fstream& file,uint16_t len);
	//find-true not find-false
	bool findKey(const uint16_t& code,const uint8_t& bit,iterator& it);
};
//DQT
//quality table
class JPEGQuality{
public:
	uint8_t precision;
	uint8_t id;
	vector<uint16_t> table;
	bool Init(fstream& file,uint16_t len);
};
//SOF segment
class JPEGComponent{
public:
	//1＝Y(jié), 2＝Cb, 3＝Cr, 4＝I, 5＝Q
	uint8_t colorId;
	uint8_t h_samp_factor;
	uint8_t v_samp_factor;
	uint8_t qualityId;
	bool Init(fstream& file,uint16_t len);
};
class JPEGData{
	int max_h_samp_factor;//行MCU
	int max_v_samp_factor;//列MCU
	int width;
	int height;
	int precision;
	bool isYUV411=false;
	bool isYUV422=false;
	bool isYUV111=false;
	uint8_t curDRI=0;//當(dāng)前重置直流分量標(biāo)識(shí),這里只取個(gè)位方便計(jì)算
	uint16_t resetInterval=0;//單位是MCU
	int preDCValue[3]={0};  //用于直流差分矯正
	//量化表
	vector<JPEGQuality> quality;
	//huffman碼表
	vector<JPEGHuffmanCode> dc_huffman;
	vector<JPEGHuffmanCode> ac_huffman;
	//component每個(gè)顏色分量
	vector<JPEGComponent> component;
	JPEGScan scan;
	//vector<int**> deHuffman;
	vector<double**> ycbcr;
	vector<RGB**> rgb;
	double** DCTAndIDCTArray;
	streampos pos;
	bool EOI{false};
public:
	JPEGData():
			max_h_samp_factor(0),
			max_v_samp_factor(0),
			width(0),
			height(0),
			precision(0){
				DCTAndIDCTArray=createDCTAndIDCTArray(ROW);
			}
	~JPEGData(){
		FREE_LP_2(DCTAndIDCTArray,ROW-1)
		// FREE_LP_2(DCTArray,ROW-1)
		// FREE_LP_2(IDCTArray,ROW-1)
		FREE_VECTOR_LP(rgb)
	}
	bool readJPEG(const char* filePath);
	int getWidth() const {return width;}
	int getHeight() const {return height;}
	vector<RGB**> getRGB() const {return rgb;}
	int getMaxHSampFactor() const {return max_h_samp_factor;}
	int getMaxVSampFactor() const {return max_v_samp_factor;}
	double** createDCTAndIDCTArray(int row);
	//double** createIDCTArray(int row);
	void DCT(double** originMatrix);
	void IDCT(double** originMatrix);
protected:
	bool readSOF(fstream& file,uint16_t len);
	bool readData(fstream& file);
	bool huffmanDecode(fstream& file);
	void deQuality(double** originMatrix,int qualityID);
	//隔行正負(fù)糾正
	void PAndNCorrect(double** originMatrix);
	RGB** YCbCrToRGB(const int* YUV);
	//標(biāo)記位檢查 是否結(jié)束,是否重置直流矯正數(shù)值，返回要添加的數(shù)值
	string FlagCkeck(fstream& file,int byteInfo);
	uint16_t ReadByte(fstream& file,int len);
	uint16_t findHuffmanCodeByBit(fstream& file,int& length,int& pos,string& deque,int curValue,int& curValLen);
};
NAME_SPACE_END()
#endif //!_IMAGE_

#include "Image.h"
#include "Util.h"
#include <algorithm>
#include <cmath>
#include <exception>
#include <fstream>
#include <stdint.h>
#include <bitset>
#include <stdlib.h>
#include <utility>
#include <cstring>
#include <vector>
#include <iomanip>
NAME_SPACE_START(myUtil)
int RGBValueLimit(double input){
    if(input<0) return 0;
    else if(input>255) return 255;
    // 四舍五入、取整均可
    // return (int)(input);
    return round(input);
}
void print(double** originMatrix){
    cout<<endl;
    for(int i=0;i<ROW;i++){
        for(int j=0;j<COL;j++){
            cout<<originMatrix[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}
double** UnZigZag(int* originArray){
    double** table=new double*[ROW];
    for(int i=0;i<ROW;i++) table[i]=new double[COL];
    int cur=0,x=0,y=0;
    bool flag = true;//true是右上 false是左下
    while (cur < 64) {
        table[y][x] = originArray[cur++];
        if (flag) { x++; y--; }
        else { x--; y++; }
        if (x < 0 || y < 0 || x>7 || y>7) flag = !flag;
        if (x < 0 && y>7) { x = 1; y = 7; }
        if (x < 0) x = 0;
        else if (x > 7) { x = 7; y += 2; }
        if (y < 0) y = 0;
        else if (y > 7) { y = 7; x += 2; }
    }
    return table;
}
bool JPEGScan::Init(fstream &file, uint16_t len){
    try {
        uint8_t count=file.get();
        len--;
        while(count--){
            uint8_t componentId=file.get();
            uint8_t table=file.get();
            uint8_t dcId=table>>4;
            uint8_t acId=table&0x0f;
            pair<uint8_t, uint8_t> info1(dcId,acId);
            pair<uint8_t, pair<uint8_t, uint8_t>> info2(componentId,info1);
            componentHuffmanMap.insert(info2);
        }
    } catch (...) {
        return false;
    }
    return true;
}
bool JPEGHuffmanCode::Init(fstream &file, uint16_t len){
    try{
        vector<uint8_t> temp;
        while(len--){
            int info=file.get();
            temp.push_back(info);
        }
        int curPos = 16, curCode = 0;
        for (int i = 0; i < 16; i++) {
            int count = temp[i];
            curCode <<= 1;
            while (count--) {
                uint16_t code=curCode;
                uint8_t bit=i+1;
                uint8_t weight=temp[curPos];
                pair<uint8_t, uint8_t> t1(bit,weight);
                pair<uint16_t, pair<uint8_t, uint8_t>> t2(curCode,t1);
                table.insert(t2);
                curCode++;
                curPos++;
            }
        }
    }
    catch(...){
        return false;
    }
    return true;
}
bool JPEGHuffmanCode::findKey(const uint16_t& code,const uint8_t& bit,iterator& it)
{
    it=table.find(code);
    if(it==table.end()) return true;
    return it->second.first!=bit;
}
bool JPEGQuality::Init(fstream &file, uint16_t len){
    try{
        int info=file.get();
        precision=info>>4;
        id=info&0x0f;
        len--;
        while(len--){
            int t=file.get();
            table.push_back(t);
        }
    }
    catch(...){
        return false;
    }
    return true;
}
bool JPEGComponent::Init(fstream &file, uint16_t len){
    try {
        int info1=file.get();
        int info2=file.get();
        int info3=file.get();
        colorId=info1;
        h_samp_factor=info2>>4;
        v_samp_factor=info2&0x0f;
        qualityId=info3;
    } catch (...) {
        return false;
    }
    return true;
}
bool JPEGData::readJPEG(const char *filePath){
    fstream file(filePath,ios::in|ios::binary);
    if(file.fail()) return false;
    file.seekg(0,ios::end);
    pos = file.tellg();
    file.seekg(2,ios::beg);
    dc_huffman.resize(2);
    ac_huffman.resize(2);
    try {
        //do read data through using other method
        uint16_t pLen=0;
        uint16_t pMarker=0xFF;
        uint16_t pType=0x00;
        while(!file.eof()){
            pMarker=file.get();
            pType=file.get();
            if(pType==EOI) break;
            pLen=file.get();
            pLen=(pLen<<8)+file.get();
            // cout<<hex<<pMarker<<" "<<pType<<" "<<pLen<<endl;
            if(pMarker!=0xFF) throw exception();
            bool flag=true;
            switch (pType) {
                case SOF0:
                case SOF1:
                case SOF2:{
                    flag=readSOF(file, pLen-2);
                    break;
                }
                case DHT:{
                    JPEGHuffmanCode huf;
                    int info=file.get();
                    int tableId=info&0x0f;
                    // cout<<hex<<info<<" ";
                    flag=huf.Init(file, pLen-3);
                    if((info>>4)&1) ac_huffman[tableId]=huf;
                    else dc_huffman[tableId]=huf;
                    break;
                }
                //case SOI:
                //case EOI:
                case SOS:{
                    flag=scan.Init(file, pLen-2);
                    int count=3;
                    // cout<<endl;
                    while(count--) file.get();
                    // cout<<endl;
                    //正式讀取數(shù)據(jù)
                    if(!flag) break;
                    flag=readData(file);
                    break;
                }
                case DQT:{
                    JPEGQuality q;
                    flag=q.Init(file, pLen-2);
                    quality.push_back(q);
                    break;
                }
                case DRI:{
                    resetInterval=ReadByte(file, 2);
                    break;
                }
                case APP0:
                case APP1:
                case APP2:
                case COM:{
                    pLen-=2;
                    while(pLen--){
                        file.get();
                    }
                    break;
                }
                default:
                    pLen-=2;
                    while(pLen--){
                        file.get();
                    }
                    break;
            }
            if(!flag) throw exception();
            // cout<<endl;
        }
    } catch (...) {
        file.close();
        return false;
    }
    file.close();
    return true;
}
bool JPEGData::readSOF(fstream& file,uint16_t len){
    try {
        precision=file.get();
        height=max(height,(int)ReadByte(file, 2));
        width=max(width,(int)ReadByte(file, 2));
        int count=ReadByte(file, 1);
        if(count!=3) return false;
        len-=6;
        component.resize(count);
        for(int i=0;i<count;i++){
            JPEGComponent com;
            com.Init(file, len/3);
            max_h_samp_factor=max(max_h_samp_factor,(int)com.h_samp_factor);
            max_v_samp_factor=max(max_v_samp_factor,(int)com.v_samp_factor);
            component[i]=com;
        }
        if((component[0].h_samp_factor*component[0].v_samp_factor)
            /(component[1].h_samp_factor*component[1].v_samp_factor)==4){
            isYUV411=true;
        }
        else if((component[0].h_samp_factor*component[0].v_samp_factor)
            /(component[1].h_samp_factor*component[1].v_samp_factor)==2){
            isYUV422=true;
        }
        else if((component[0].h_samp_factor*component[0].v_samp_factor)
            /(component[1].h_samp_factor*component[1].v_samp_factor)==1){
            isYUV111=true;
        }
    } catch (...) {
        return false;
    }
    return true;
}
bool JPEGData::readData(fstream& file){
    bool flag=true;
    try{
        //使用huffman表來(lái)解出RLE編碼，接著轉(zhuǎn)回長(zhǎng)度為64的矩陣
        flag=huffmanDecode(file);
        if(!flag) return false;
        //反量化，即上面的64矩陣×對(duì)應(yīng)位置的量化表
        //flag=deQuantity();
        //if(!flag) return false;
        //反zig-zag排序
        //flag=deZSort();
        //if(!flag) return false;
        //反離散余弦變換
        //if(!flag) return false;
        //YCbCr轉(zhuǎn)RGB
        //if(!flag) return false;
    }
    catch(...){
        return false;
    }
    return true;
}
bool JPEGData::huffmanDecode(fstream& file){
    try {
        //原圖像一個(gè)MCU有多少8*8矩陣（此時(shí)是YCbCr還沒(méi)有分開(kāi)）
        //int MCUBlockCount=max_h_samp_factor*max_v_samp_factor;
        //順序YCbCr
        int YUV[]={component[0].h_samp_factor*component[0].v_samp_factor,
                    component[1].h_samp_factor*component[1].v_samp_factor,
                    component[2].h_samp_factor*component[2].v_samp_factor};
        int curMCUCount=1;      //當(dāng)前MCU數(shù)量
        int curValueLength=0;   //當(dāng)前值有多少位
        int curValue=0;         //當(dāng)前的值
        int curBitDequeLength=8;//當(dāng)前curBitDeque長(zhǎng)度
        int curBitPos=0;        //當(dāng)前string讀取到第幾位
        int restart=resetInterval;//直流分量重置
        string curBitDeque="";  //用來(lái)存儲(chǔ)讀出來(lái)的2進(jìn)制數(shù)
        //一次循環(huán)解析一個(gè)MCU
        curBitDeque.append(bitset<8>(file.get()).to_string());
        curBitDequeLength=8;
        // cout<<curBitDeque;
        while(!EOI||(pos-file.tellg())!=2){
            // cout<<endl;
            int count=1;
            for(int i=0;i<3;i++){
                for(int j=0;j<YUV[i];j++){
                    // cout<<count++<<" ";
                    int matrix[64]={0};
                    int valCount=0;
                    uint8_t dcID = scan.componentHuffmanMap[component[i].colorId].first;
                    uint8_t acID = scan.componentHuffmanMap[component[i].colorId].second;
                    int qualityId=component[i].qualityId;
                    if(qualityId>=quality.size()) qualityId=0;
                    // cout<<endl;
                    while(valCount<64){
                        //用curBitDeque和curBit去找權(quán)重，curValue作為當(dāng)前鍵值
                        JPEGHuffmanCode::iterator it;
                        JPEGHuffmanCode &huffman = valCount==0?dc_huffman[dcID]:ac_huffman[acID];
                        while(curValueLength<=16&&huffman.findKey(curValue,curValueLength,it)){
                            curValue=findHuffmanCodeByBit(file,curBitDequeLength,curBitPos,curBitDeque,curValue,curValueLength);
                        }
                        if(curValueLength>16) 
                            return true;
                        #ifdef _DEBUGOUT_
                        //cout<<dec<<" "<<curBitPos<<" "<<curBitDequeLength<<" ";
                        cout<<"key="<<hex<<curValue<<" len="<<curValueLength<<endl;
                        #endif
                        //已經(jīng)找到了權(quán)重和位寬
                        uint8_t weight,zeroCount=0;
                        if(valCount==0) weight = it->second.second;
                        else { weight = it->second.second & 0x0f; zeroCount = it->second.second >> 4;}
                        curValue=0;//這里變?yōu)閐c或ac值
                        curValueLength=0;
                        if(valCount!=0&&weight==0&&zeroCount==0) break;//后面全是0
                        // 讀取真正的值
                        for(int k=0;k<weight;k++){
                            curValue=findHuffmanCodeByBit(file,curBitDequeLength,curBitPos,curBitDeque,curValue,curValueLength);
                        }
                        curValue = (curValue >= pow(2, curValueLength - 1) ? curValue : curValue - pow(2, curValueLength) + 1);
                        // cout<<curValue<<endl;
                        int writeValue=valCount==0?(preDCValue[i]+=curValue):curValue;
                        valCount+=zeroCount;
                        writeValue*=quality[qualityId].table[valCount];//反量化
                        matrix[valCount]=writeValue;
                        curValue=0;
                        curValueLength=0;
                        valCount++;
                    }
                    double** tempZ = UnZigZag(matrix);//反zig-zag編碼
                    //反量化，在反zig-zag編碼前后差別，前面：RGB數(shù)值與編輯器比偏小，反之偏大，這也與最后取整時(shí)的方式有關(guān)
                    // deQuality(tempZ,qualityId);
                    // print(tempZ);
                    //隔行正負(fù)糾正，有的博客說(shuō)了，但是沒(méi)感覺(jué)有啥幫助
                    // PAndNCorrect(tempZ);
                    IDCT(tempZ);                    //dct逆變換
                    ycbcr.push_back(tempZ);
                #ifdef _DEBUG_
                    for(int k=0;k<ROW;k++){
                        for(int l=0;l<COL;l++){
                            cout.width(3);
                            cout<<dec<<tempZ[k][j]<<" ";
                        }
                        cout<<endl;
                    }
                    cout<<endl;
                #endif
                }
            }
            // if(count!=6){
            //     cout<<" ";
            // }
            RGB** lpRGB = YCbCrToRGB(YUV);
            FREE_VECTOR_LP(ycbcr)
            rgb.push_back(lpRGB);
            // 直流分量重置間隔不為0的
            if(restart>0){
                resetInterval--;
                if(resetInterval==0){
                    resetInterval=restart;
                    curDRI+=1;
                    curDRI&=0x7;
                    //需要在此處讀取兩字節(jié)信息，看是否為重置標(biāo)識(shí)
                    file.get();
                    if(file.get()==0xD9) EOI=true;
                    curBitPos=curBitDequeLength;
                    preDCValue[0]=0;
                    preDCValue[1]=0;
                    preDCValue[2]=0;
                }
            }
            // cout<<"curMCUCount="<<dec<<curMCUCount++<<" pos="<<pos<<"/"<<file.tellg()<<" "<<file.tellg()*100.0/pos<<"%\n";
            if(pos-file.tellg()==2) break;
        }
        cout<<"\nsuccessfully\n";
    } catch (exception ex) {
        cout<<ex.what();
        return false;
    }
    return true;
}
RGB** JPEGData::YCbCrToRGB(const int* YUV){
    RGB **res = new RGB *[ROW * max_v_samp_factor];
    int matrixCount = YUV[0] + YUV[1] + YUV[2];
    int crCount = 0, cbCount = 0;
    //1＝Y(jié), 2＝Cb, 3＝Cr
    //式子 scale*x,scale*y
    double cb_h_samp_scale=component[1].h_samp_factor*1.0/max_h_samp_factor,
           cb_v_samp_scale=component[1].v_samp_factor*1.0/max_v_samp_factor,
           cr_h_samp_scale=component[2].h_samp_factor*1.0/max_h_samp_factor,
           cr_v_samp_scale=component[2].v_samp_factor*1.0/max_v_samp_factor;
    for (int i = 0; i < ROW * max_v_samp_factor; i++)
        res[i] = new RGB[COL * max_h_samp_factor];
    //此處直接生成rgb值
    //注意，此處YCbCr的對(duì)應(yīng)關(guān)系與采樣因子有關(guān)
    // cout<<endl;
    for(int j=0;j<ROW * max_v_samp_factor;j++){
        for(int k=0;k<COL * max_h_samp_factor;k++){
            int yPos = (j / ROW) * component[0].h_samp_factor + (k / COL);
            int cbPos = YUV[0] + (int)((k / ROW) * cb_v_samp_scale) + (int)((j / COL) * cb_h_samp_scale);
            int crPos = YUV[0] + YUV[1] + (int)((k / ROW) * cr_v_samp_scale) + (int)((j / COL) * cr_h_samp_scale);
            double y = ycbcr[yPos][j % ROW][k % COL];
            double cb = ycbcr[cbPos][(int)(j * cb_v_samp_scale)][(int)(k * cb_h_samp_scale)];
            double cr = ycbcr[crPos][(int)(j * cr_v_samp_scale)][(int)(k * cr_h_samp_scale)];
            res[j][k].red   =RGBValueLimit(128+y+1.402  *cr);
            res[j][k].green =RGBValueLimit(128+y-0.71414*cr-0.34414*cb);
            res[j][k].blue  =RGBValueLimit(128+y+1.772  *cb);
            // 輸出當(dāng)前選擇的矩陣
            //cout<<dec<<yPos<<" "<<cbPos<<" "<<crPos<<" ";
            // cout<<hex<<setw(2)<<setfill('0')<<(int)res[j][k].red
            //          <<setw(2)<<setfill('0')<<(int)res[j][k].green
            //          <<setw(2)<<setfill('0')<<(int)res[j][k].blue<<" ";
        }
        // cout<<endl;
    }
    // cout<<endl;
    return res;
}
double** JPEGData::createDCTAndIDCTArray(int row){
    double** res=new double*[row];
    for(int i=0;i<row;i++) res[i]=new double[row];
    // cout<<endl;
    for(int i=0;i<row;i++){
        for(int j=0;j<row;j++){
            double t=0;
            if(i==0) t=sqrt(1.0/row);
            else t=sqrt(2.0/row);
            res[i][j]=t*cos(M_PI*(j+0.5)*i/row);
            // cout<<res[i][j]<<" ";
        }
        // cout<<endl;
    }
    return res;
}
void JPEGData::DCT(double** originMatrix){
    //原理 Y=A*X*A'
    vector<vector<double>> temp(ROW,vector<double>(COL,0));
    for(int i=0;i<ROW;i++){
        for(int j=0;j<COL;j++){
            double sum=0;
            for(int k=0;k<COL;k++){
                sum+=DCTAndIDCTArray[i][k]*originMatrix[k][j];
            }
            temp[i][j]=sum;
        }
    }
    for(int i=0;i<ROW;i++){
        for(int j=0;j<COL;j++){
            double sum=0;
            for(int k=0;k<COL;k++){
                sum+=temp[i][k]*DCTAndIDCTArray[j][k];
            }
            originMatrix[i][j]=sum;
        }
    }
}
void JPEGData::IDCT(double** originMatrix){
    //原理X=A'*Y*A
    vector<vector<double>> temp(ROW,vector<double>(COL,0));
    for(int i=0;i<ROW;i++){
        for(int j=0;j<COL;j++){
            double sum=0;
            for(int k=0;k<COL;k++){
                sum+=DCTAndIDCTArray[k][i]*originMatrix[k][j];
            }
            temp[i][j]=sum;
        }
    }
    for(int i=0;i<ROW;i++){
        for(int j=0;j<COL;j++){
            double sum=0;
            for(int k=0;k<COL;k++){
                sum+=temp[i][k]*DCTAndIDCTArray[k][j];
            }
            originMatrix[i][j]=sum;
        }
    }
}
void JPEGData::deQuality(double** originMatrix,int qualityID){
    for(int i=0;i<ROW;i++){
        for(int j=0;j<COL;j++){
            originMatrix[i][j]*=quality[qualityID].table[i*ROW+j];
        }
    }
}
void JPEGData::PAndNCorrect(double** originMatrix){
    for(int i=0;i<ROW;i++)
        if(i%2==1)
            for(int j=0;j<COL;j++) 
                originMatrix[i][j]=-originMatrix[i][j];
}
string JPEGData::FlagCkeck(fstream& file,int byteInfo){
    if(byteInfo==0xff){
        uint8_t info=file.get();
        string res=bitset<8>(0xFF).to_string();
        if(info==0xD9) {EOI=true;return "false";}
        else if(info==0x00) return res;
        return res + bitset<8>(info).to_string();
    }
    return bitset<8>(byteInfo).to_string();
}
uint16_t JPEGData::ReadByte(fstream& file,int len){
    uint16_t res=file.get();
    if(len!=1){
        res=(res<<8)+(uint8_t)file.get();
    }
    return res;
}
uint16_t JPEGData::findHuffmanCodeByBit(fstream& file,int& length,int& pos,string& deque,int curValue,int& curValLen){
    if(pos==length&&length>=HUFFMAN_DECODE_DEQUE_CACHE){//達(dá)到最大緩存
        deque = deque.substr(pos);
        int info=file.get();
        string res=FlagCkeck(file,info);
        string str=bitset<8>(info).to_string();
        if(res=="false") res=bitset<8>(file.get()).to_string();
        deque.append(res);
        length = deque.length();
        pos = 0;
    }
    else if(length==0 || pos>=length){
        if(length==0){
            deque="";
            pos=0;
        }
        int info=file.get();
        string res=FlagCkeck(file,info);
        string str=bitset<8>(info).to_string();
        if(res=="false") res=bitset<8>(file.get()).to_string();
        deque.append(res);
        length+=8;
    }
    curValue = (curValue << 1) + (uint8_t)(deque.at(pos++) - '0');
    curValLen++;
    return curValue;
}
NAME_SPACE_END()

#pragma once
#include <stdio.h>
#include <iostream>
#include "Image.h"
using namespace myUtil;
/* Bitmap Header, 54 Bytes  */
static 
unsigned char BmpHeader[54] = 
{
	0x42, 0x4D, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x36, 0x00, 0x00, 0x00, 0x28, 0x00,
	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1B, 0x01, 0x00, 0x00, 0x01, 0x00, 0x18, 0x00, 0x00, 0x00,
	0x00, 0x00, 0x60, 0xCD, 0x04, 0x00, 0x23, 0x2E, 0x00, 0x00, 0x23, 0x2E, 0x00, 0x00, 0x00, 0x00,
	0x00, 0x00, 0x00, 0x00, 0x00, 0x00
};
void SetBitmapInfo(unsigned int size, int height, int width)
{
	for (int i = 0; i < 4; i++)
	{
		// size of image ( header + data )
		BmpHeader[2 + i] = size & 0xff;
		size >>= 8;
		// width of image
		BmpHeader[18 + i] = width & 0xff;
		width >>= 8;
		// height of image
		BmpHeader[22  + i] = height & 0xff;
		height >>= 8;
	}
}
/* BGR format 這是我粘來(lái)的改了映射部分代碼 */
unsigned char *Encoder(const vector<RGB**>& buf, int height, int width, int mcu_height, int mcu_width, int &size)
{
	uint8_t *bitmap = nullptr;
	int rowSize = (24 * width + 31) / 32 * 4;
	// compute the size of total bytes of image
	size = rowSize * height + 54; // data size + header size
	bitmap = new uint8_t [ size ];
	// set the header info
	SetBitmapInfo(size, height, width);
	// fill the header area
	for (int i = 0; i < 54; i++)
	{
		bitmap[i] = BmpHeader[i];
	}
	// fill the data area
	for (int i = 0; i < height; i++)
	{
		// compute the offset of destination bitmap and source image
		int idx = height - 1 - i;
		int offsetDst = idx * rowSize + 54; // 54 means the header length
		// int offsetSrc = i * width;
		int offsetHeight = (int)floor(i*1.0/mcu_height)*(int)ceil(width*1.0/mcu_width);
		// fill data
		for (int j = 0; j < width * 3; j++)
		{
			int pos=(j/3)/mcu_width+offsetHeight;
			if(pos>=buf.size()) pos=buf.size()-1;
			RGB temp=buf[pos][i%mcu_height][(j/3)%mcu_height];
			if(j%3==0) bitmap[offsetDst + j] = temp.blue;
			else if(j%3==1) bitmap[offsetDst + j] = temp.green;
			else if(j%3==2) bitmap[offsetDst + j] = temp.red;
			// cout<<dec<<pos<<" ";
		}
		// fill 0x0, this part can be ignored
		for (int j = width * 3; j < rowSize; j++)
		{
			bitmap[offsetDst +j] = 0x0;
		}
	}
	return bitmap;
}
/* Save to file */
void Write(const char *fileName, uint8_t *buf, int &size)
{
	FILE *fp = fopen(fileName, "wb+");
	fwrite(buf, 1, size, fp);
	fclose(fp);
}

#include <algorithm>
#include <cctype>
#include <fstream>
#include <iostream>
#include <locale>
#include <sstream>
#include <stdlib.h>
#include "Image.h"
#include "BmpEncoder.h"
using namespace std;
using namespace myUtil;
// void print(double** input){
// 	cout<<endl;
// 	for(int i=0;i<8;i++){
// 		for(int j=0;j<8;j++){
// 			cout<<input[i][j]<<" ";
// 		}
// 		cout<<endl;
// 	}
// 	cout<<endl;
// }
int main(){
	string str="../img/Image/3.jpg";
	JPEGData data;
	clock_t startTime=clock();
	data.readJPEG(str.c_str());
	int size;
	unsigned char *bitmap = Encoder(data.getRGB(), data.getHeight(), data.getWidth(),
								8*data.getMaxHSampFactor(),
								8*data.getMaxVSampFactor(), size);
	Write("out.bmp", bitmap, size);
	cout<<dec<<clock()-startTime<<"ms"<<endl;
	// DCT正反變換測(cè)試
	// JPEGData data;
	// double** arr=new double*[8];
	// for(int i=0;i<8;i++){
	// 	arr[i]=new double[8];
	// 	for(int j=0;j<8;j++){
	// 		arr[i][j]=(int)(rand()%100);
	// 	}
	// }
	// print(arr);
	// data.DCT(arr);
	// print(arr);
	// data.IDCT(arr);
	// print(arr);
	// FREE_LP_2(arr,8)
    return 0;
}