Makset
Reputation: 11
Malformed PNG pixel data from deflate "unknown edge cases"
For the past 2 months, I've been implementing a png/deflate decoder, (for various reasons but mainly for learning purposes) but only returns the correct expected data in some cases.
Here in this table, I've gathered some details of the files (and the files themselves) that I've been using for the program in case you want to check them out:
| State | Image | Block type | Lz77 obtained (if fail) | Header info (Block type 2 only) |
|---|---|---|---|---|
| Works | Color checker pattern | 2 | HLIT: 29, HDIST: 23, HCLEN: 14, Header cls: {0,3,3,3,3,4,0,4,0,3,0,4,0,4,0,4,0,4} | |
| Works | A grid with grayscale pixels | 1 | ||
| Doesn't work | 10x10 noise image | 2 | 0 0 0 1 2 257 4 0 3 1 4 0 5 6 7 8 0 9 10 11 0 12 0 3 0 13 14 1 15 0 1 16 17 258 -fails here [ 9 11 ] -Program attempts to read 36 symbols backwards on a 33 sized list | HLIT: 2, HDIST: 13, HCLEN: 12, Header cls: {2,4,4,4,0,2,0,4,0,5,0,5,0,4,0,3} |
| Doesn't work |  |
1 | 1 255 255 255 0 260 0 1 1 261 6 0 0 0 183 262 8 3 2 261 5 1 270 0 0 272 0 9 6 51 255 176 266 0 -fails here [ 26 141 ] -Program attempts to read 8334 symbols backwards on a 34 sized list | |
| Returns malformed data | Some random colors | 2 | Possibly some data was malformed | HLIT: 4, HDIST: 10, HCLEN: 14, Header cls: {0,4,3,3,0,0,0,3,0,4,0,3,0,2,0,4,0,4} |
Here is a snippet (or a MRE) of how I implemented deflate (The program needs the image path as a parameter; I tried my best to get it working with the fewest lines of code):
#include <stdio.h>
#include <math.h>
#include <stdint.h>
#include <stdlib.h>
//Quick table for ll distinction
uint16_t qtfld[5][2] = {
{269,1},{273,2},
{277,3},{281,4},
{285,5}
};
//Quick table for distance distinction
uint8_t qtfdd[13][2] = {
{6,1},{8,2},{9,3},
{12,4},{14,5},{16,6},
{18,7},{20,8},{22,9},
{24,10},{26,11},{28,12},
{30,13}
};
uint32_t FlipEndian(
uint32_t value,
uint32_t SToFlip
){
if(SToFlip==0){return 0;}
else{
uint32_t reversed = 0;
for(uint32_t w = 0; w <= SToFlip; w++){
uint32_t lshift = 0;
uint32_t rshift = 0;
lshift = value<<(31-w);
rshift = lshift>>31;
reversed = (rshift<<((SToFlip-1)-w)) | reversed;
}
return reversed;
}
}
uint16_t** GenCodes(
uint16_t* cl_table,
uint16_t* symbol_table,
uint32_t both_tables_size
){
//Finaltable
uint32_t sizecodes = both_tables_size * sizeof(uint16_t*);
uint16_t** codes = (uint16_t**)malloc(sizecodes);
for(uint32_t i=0; i<both_tables_size; i++){
codes[i] = (uint16_t*)malloc(3*sizeof(uint16_t));
}
//List for the sorting and frequency obtaining of the cl codes
uint32_t size = both_tables_size*sizeof(uint16_t);
int16_t* used_cls = (int16_t*)malloc(size);
for(uint32_t i=0; i<both_tables_size; i++){
used_cls[i] = -1;
}
//The aforementioned sorted cl table
uint32_t cl_amount = 15*sizeof(uint16_t*);
uint16_t** sorted_cl_frequencies = (uint16_t**)malloc(cl_amount);
for(uint32_t c=0; c<15; c++){
sorted_cl_frequencies[c] = (uint16_t*)malloc(2*sizeof(uint16_t));
}
for(uint32_t i=0; i<both_tables_size; i++){
uint16_t min_cl = 15;
uint8_t cl_usage = 0;
for(uint32_t j=0; j<both_tables_size; j++){
uint16_t current_cl = cl_table[i];
for(uint32_t k=0; k<both_tables_size; k++){
if(current_cl == used_cls[k]){
cl_usage = 1;
break;
}
}
if(cl_usage==0){
if(current_cl<min_cl){min_cl = current_cl;}
}
}
if(cl_usage==0){
uint32_t cl_counter = 0;
for(uint32_t a=0; a<both_tables_size; a++){
if(cl_table[a]==min_cl){cl_counter++;}
}
sorted_cl_frequencies[min_cl][0] = min_cl;
sorted_cl_frequencies[min_cl][1] = cl_counter;
used_cls[i] = min_cl;
}
}
//Huffman code algorithm
uint16_t code = 0;
for(uint32_t i = 1; i <= 15; i++) {
if(i<15){
uint16_t prevfreq = sorted_cl_frequencies[i-1][1];
uint16_t prevcl = sorted_cl_frequencies[i][0];
code = (code + prevfreq) << 1;
uint16_t aum = 0;
for(uint32_t j = 0;j<both_tables_size;j++){
if(prevcl==cl_table[j]){
codes[j][0] = symbol_table[j];
codes[j][1] = cl_table[j];
codes[j][2] = FlipEndian(code+aum,cl_table[j]);
aum+=1;
}
}
}
}
for(uint8_t i=0; i<15; i++){
free(sorted_cl_frequencies[i]);
}
free(used_cls);
free(sorted_cl_frequencies);
return codes;
}
//OverallSlicedDataGathering
uint16_t OSDG(
uint8_t* list,
uint32_t* biotl, //bitindexonthelist
uint8_t sogd //sizeofgivendata
){
uint32_t currentbyte = (uint32_t)floor((*biotl/8));
uint32_t landingbyte = (uint32_t)floor((((*biotl-1)+sogd)/8));
uint16_t final_data = 0;
if(landingbyte>currentbyte){
if(landingbyte>(currentbyte+1)){
uint8_t bocb = 8-(*biotl%8);//bitsoncurrentbyte
uint8_t slice1 = list[currentbyte]>>(8-bocb);
uint8_t bonb = sogd-bocb;//bitsonnextbyte
uint8_t slice2 = list[landingbyte] << (8-bonb);
slice2 = slice2>>(8-bonb);
uint16_t walls = 0;
uint8_t middleslice = list[currentbyte+1];
walls = (slice2<<(bocb+8)) | (middleslice<<bocb) | slice1;
final_data = walls;
}
else{
uint8_t bocb = 8-(*biotl%8);//bitsoncurrentbyte
uint8_t slice1 = list[currentbyte]>>(8-bocb);
uint8_t bonb = sogd-bocb;//bitsonnextbyte
uint8_t slice2 = list[landingbyte] << (8-bonb);
slice2 = slice2>>(8-bonb);
uint16_t walls = 0;
walls = (slice2<<(bocb)) | slice1;
final_data = walls;
}
}
else{
//alongpartsifthereis
uint8_t apiti = (*biotl%8)+sogd;
//ShapedData
uint8_t sd = list[currentbyte] << (8-apiti);
sd = sd >> (8-sogd);
final_data = (uint16_t)sd;
}
*biotl += sogd;
return final_data;
}
uint16_t* Obtain_CL_From_Bistream(
uint16_t encoded_cls,
uint16_t** codes,
uint32_t size_of_codes,
uint32_t* bit_index,
uint8_t* idat_pointer
){
uint32_t size = sizeof(uint16_t)*encoded_cls;
uint16_t* finaltable = (uint16_t*)malloc(size);
//skippedllsymbols
int16_t sls = -1;
for(uint16_t i=0; i<encoded_cls; i++){
if(i>sls){
for(uint32_t j=0; j<size_of_codes; j++){
uint16_t cc = codes[j][2]; //currentcode
uint16_t ccl = codes[j][1]; //currentcodelength
uint16_t ccs = codes[j][0]; //currentcodesymbol
//retrievedsymbolcodefrombitstream
uint8_t rscfb = OSDG(idat_pointer,bit_index,ccl);
*bit_index-= ccl;
if(rscfb==cc){
*bit_index += ccl;
//amountofsymbols
uint16_t aos = 0;
if(ccs==16){
uint8_t ntb = OSDG(idat_pointer,bit_index,2);
aos = (ntb+3);
//previoussymbol
uint16_t ps = (uint16_t)(finaltable[i-1]);
for(uint16_t x=0 ;x<=aos; x++){
finaltable[i+x] = ps;
}
}
else if(ccs==17){
//nextthreebits
uint8_t ntrb = OSDG(idat_pointer,bit_index,3);
aos = (ntrb+3);
for(uint16_t x=0; x<=aos; x++){
finaltable[i+x] = (uint16_t)(0);
}
}
else if(ccs==18){
//nextsevenbits
uint8_t nsb = OSDG(idat_pointer,bit_index,7);
aos = (nsb+11);
for(uint16_t x=0; x<=aos; x++){
finaltable[i+x] = (uint16_t)(0);
}
}
else{
aos = 1;
finaltable[i] = (uint16_t)(ccs);
}
sls += aos;
break;
}
}
}
}
return finaltable;
}
uint16_t* Uncompressed(
uint32_t* bit_index,
uint8_t* idat_pointer,
uint32_t arbitrary_size
){
*bit_index += 5;
uint16_t len1 = idat_pointer[(uint32_t)floor((*bit_index/8))];
uint16_t len2 = idat_pointer[(uint32_t)floor((*bit_index/8))+1];
uint16_t LEN = (len1<<8)|(len2);
*bit_index += 16;
uint16_t nlen1 = idat_pointer[(uint32_t)floor((*bit_index/8))];
uint16_t nlen2 = idat_pointer[(uint32_t)floor((*bit_index/8))+1];
uint16_t NLEN = ~((nlen1<<8)|(nlen2));
*bit_index += 16;
uint32_t size = arbitrary_size*(sizeof(uint16_t));
uint16_t* data = (uint16_t*)malloc(size);
for(uint32_t i = 0; i<arbitrary_size; i++){
data[i] = 0;
}
if(LEN==NLEN){
for(uint32_t i = 0; i<arbitrary_size; i++){
data[i] = OSDG(idat_pointer,bit_index,8);
}
}
return data;
}
uint16_t* Static(
uint32_t* bit_index,
uint8_t* idat_pointer,
uint32_t arbitrary_size
){
uint32_t size = arbitrary_size*(sizeof(uint16_t));
uint16_t* data = (uint16_t*)malloc(size);
uint8_t EOT_found=0;
for(uint32_t i=0; i<arbitrary_size; i++){
if(EOT_found){break;}
uint8_t ignore=0;
//newobtainedfixedvaluefrombitstream
int16_t nofvfb = (int16_t)OSDG(idat_pointer,bit_index,8);
nofvfb = FlipEndian(nofvfb,8);
*bit_index-=8;
if((nofvfb-48)<=143 && (nofvfb-48)>=0){
*bit_index+=8;
data[i] = (nofvfb-48);
ignore=1;
}
nofvfb = (int16_t)OSDG(idat_pointer,bit_index,9);
nofvfb = FlipEndian(nofvfb,9);
*bit_index-=9;
if((nofvfb-256)<=255 && (nofvfb-256)>=144){
if(ignore==0){
data[i] = (nofvfb-256);
*bit_index+=9;
ignore=1;
}
}
nofvfb = (int16_t)OSDG(idat_pointer,bit_index,7);
nofvfb = FlipEndian(nofvfb,7);
*bit_index-=7;
if((nofvfb+256)<=279 && (nofvfb+256)>=256){
if(ignore==0){
*bit_index+=7;
if((nofvfb+256)!=256){
data[i] = (nofvfb+256);
ignore=1;
if((nofvfb+256)>264 && (nofvfb+256)<285){
for(uint32_t j=0;j<5;j++){
if((nofvfb+256)<qtfld[j][0]){
i+=1;
//readoffsetbitsoflength
uint8_t robol = (uint8_t)OSDG(idat_pointer,bit_index,qtfld[j][1]);
data[i] = robol;
break;
}
}
}
i+=1;
//distancereturnedvaluebybits
uint8_t drvbb = (uint8_t)OSDG(idat_pointer,bit_index,5);
drvbb = FlipEndian(drvbb,5);
data[i] = drvbb;
if(drvbb>3){
for(uint32_t k=0;k<13;k++){
if(drvbb<qtfdd[k][0]){
i+=1;
//readoffsetbitsofdistance
uint8_t robod = (uint8_t)OSDG(idat_pointer,bit_index,qtfdd[k][1]);
data[i] = robod;
break;
}
}
}
}
else{
data[i] = (nofvfb+256);
ignore=1;
EOT_found=1;
}
}
}
nofvfb = (int16_t)OSDG(idat_pointer,bit_index,8);
nofvfb = FlipEndian(nofvfb,8);
*bit_index-=8;
if((nofvfb+88)<=287 && (nofvfb+88)>=280){
if(ignore==0){
*bit_index+=8;
data[i] = (nofvfb+88);
ignore=1;
if((nofvfb+88)>264 && (nofvfb+88)<285){
for(uint32_t j=0;j<5;j++){
if((nofvfb+88)<qtfld[j][0]){
i+=1;
//readoffsetbitsoflength
uint8_t robol = (uint8_t)OSDG(idat_pointer,bit_index,qtfld[j][1]);
data[i] = robol;
break;
}
}
}
i+=1;
//distancereturnedvaluebybits
uint8_t drvbb = (uint8_t)OSDG(idat_pointer,bit_index,5);
drvbb = FlipEndian(drvbb,5);
data[i] = drvbb;
if(drvbb>3){
for(uint32_t k=0;k<13;k++){
if(drvbb<qtfdd[k][0]){
i+=1;
//readoffsetbitsofdistance
uint8_t robod = (uint8_t)OSDG(idat_pointer,bit_index,qtfdd[k][1]);
data[i] = robod;
break;
}
}
}
}
}
}
return data;
}
uint16_t* Dynamic(
uint32_t* bit_index,
uint8_t* idat_pointer,
uint32_t arbitrary_size
){
uint8_t HLIT = (uint8_t)OSDG(idat_pointer,bit_index,5);
printf("\nHLIT: %d",HLIT);
uint8_t HDIST = (uint8_t)OSDG(idat_pointer,bit_index,5);
printf("\nHDIST: %d",HDIST);
uint8_t HCLEN = (uint8_t)OSDG(idat_pointer,bit_index,4);
printf("\nHCLEN: %d",HCLEN);
uint16_t newcl_clorder[19] = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
//List of CLs
uint16_t* CL_cl_lengths = (uint16_t*)malloc(sizeof(uint16_t)*(HCLEN + 4));
printf("\nHeader cls\n");
uint8_t not_zero_cls_counter = 0;
for(uint32_t i = 0; i < (HCLEN + 4); i++){
uint8_t CL_cl = (uint8_t)OSDG(idat_pointer,bit_index,3);
CL_cl_lengths[newcl_clorder[i]] = CL_cl;
printf("%d,",CL_cl_lengths[newcl_clorder[i]]);
if(CL_cl!=0){
not_zero_cls_counter++;
}
}
uint32_t size = sizeof(uint16_t)*not_zero_cls_counter;
//sorted header cl symbols
uint16_t* shcs = (uint16_t*)malloc(size);
//sorted header cl cl
uint16_t* shcc = (uint16_t*)malloc(size);
int8_t* used_cls = (int8_t*)malloc(sizeof(int8_t)*not_zero_cls_counter);
for(uint8_t i=0; i<not_zero_cls_counter; i++){used_cls[i]=-1;}
for(uint8_t i=0; i<not_zero_cls_counter; i++){
uint8_t smallestsymbol = 18;
uint8_t smallestsymbol_index = 2;
for(uint8_t j=0; j<(HCLEN + 4); j++){
uint8_t used_cls_usage = 0;
uint16_t newavailablesymbol = newcl_clorder[j];
for(uint8_t k=0; k<not_zero_cls_counter; k++){
if(newavailablesymbol==used_cls[k]){
used_cls_usage = 1;
break;
}
}
if(used_cls_usage==0){
uint8_t newsymbcl = CL_cl_lengths[newcl_clorder[j]];
if(newavailablesymbol<smallestsymbol && newsymbcl != 0){
smallestsymbol = newavailablesymbol;
smallestsymbol_index = j;
}
}
}
shcs[i] = newcl_clorder[smallestsymbol_index];
shcc[i] = CL_cl_lengths[newcl_clorder[smallestsymbol_index]];
used_cls[i] = newcl_clorder[smallestsymbol_index];
}
uint16_t** header_cl_symbols = GenCodes(shcc,shcs,not_zero_cls_counter);
///////////Obtainingofllcodes
uint16_t* zeroed_ll_cls = Obtain_CL_From_Bistream(
(257+HLIT),header_cl_symbols,
not_zero_cls_counter,
bit_index,idat_pointer
);
uint16_t* ll_cl = (uint16_t*)malloc(sizeof(uint16_t)*288);
uint16_t* ll_symbols = (uint16_t*)malloc(sizeof(uint16_t)*288);
//finalsizeofnotzeroedlls
uint32_t fsonzl = 0;
uint32_t ll_omitter = 0;
for(uint32_t i=0; i<(257+HLIT);i++){
if(zeroed_ll_cls[i]!=0){
ll_cl[i-ll_omitter] = zeroed_ll_cls[i];
ll_symbols[i-ll_omitter]=i;
fsonzl+=1;
}
else{ll_omitter+=1;}
}
uint16_t** ll_codes = GenCodes(ll_cl,ll_symbols,fsonzl);
printf("\nLL generated codes:");
for(uint32_t l=0; l<fsonzl; l++){
printf("\nsymbol: %d, ",ll_codes[l][0]);
printf("cl: %d, ",ll_codes[l][1]);
printf("code: %d",ll_codes[l][2]);
}
///////////Obtainingofdistcodes
uint16_t* zeroed_dist_cls = Obtain_CL_From_Bistream(
(HDIST+1),header_cl_symbols,
not_zero_cls_counter,
bit_index,idat_pointer
);
uint16_t* dist_cl = (uint16_t*)malloc(sizeof(uint16_t)*32);
uint16_t* dist_symbols = (uint16_t*)malloc(sizeof(uint16_t)*32);
//finalsizeofnotzeroeddist
uint32_t fsonzd = 0;
uint32_t dist_omitter = 0;
for(uint32_t i=0; i<(HDIST+1);i++){
if(zeroed_dist_cls[i]!=0){
dist_cl[i-dist_omitter] = zeroed_dist_cls[i];
dist_symbols[i-dist_omitter] = i;
fsonzd+=1;
}
else{dist_omitter+=1;}
}
uint16_t** dist_codes = GenCodes(dist_cl,dist_symbols,fsonzd);
printf("\nDistance generated codes:");
for(uint32_t d=0; d<fsonzd; d++){
printf("\nsymbol: %d, ",dist_codes[d][0]);
printf("cl: %d, ",dist_codes[d][1]);
printf("code: %d",dist_codes[d][2]);
}
///////////bitstreamdecryption
uint32_t bsize = arbitrary_size*(sizeof(uint16_t));
uint16_t* data = (uint16_t*)malloc(bsize);
for(uint32_t i=0; i<arbitrary_size; i++){data[i]=0;}
int ofsfld = -1;
uint8_t megabreak = 0;
for(int i=0; i<arbitrary_size; i++){
if(megabreak==1){break;}
if(i>ofsfld){
for(uint16_t j=0; j<=fsonzl; j++){
uint16_t cc = ll_codes[j][2]; //currentcode
uint16_t ccl = ll_codes[j][1]; //currentcodelength
uint16_t ccs = ll_codes[j][0]; //currentcodesymbol
//retrievedllsymbolcodefrombistream
uint16_t rlscfb = OSDG(idat_pointer,bit_index,ccl);
*bit_index -= ccl;
if(rlscfb==cc){
*bit_index += ccl;
data[i] = ccs;
ofsfld+=1;
if(ccs==256){megabreak=1;break;}
if(ccs>256){
uint8_t aum = 0;
if(ccs>264 && ccs!=285){
for(uint8_t t=0; t<5; t++){
if(ccs<qtfld[t][0]){
//readoffset
data[(i+1)] = OSDG(idat_pointer,bit_index,qtfld[t][1]);
aum=1;
ofsfld+=1;
break;
}
}
}
for(uint32_t k=0; k<=fsonzd; k++){
uint16_t dcc = dist_codes[k][2]; //distancecc
uint16_t dccl = dist_codes[k][1]; //distanceccl
uint16_t dccs = dist_codes[k][0]; //distanceccs
//retrieveddistancesymbolcodefrombistream
uint8_t rdscfb = OSDG(idat_pointer,bit_index,dccl);
*bit_index -= dccl;
if(rdscfb==dcc){
*bit_index += dccl;
ofsfld += 1;
data[(i+(1+aum))] = dccs;
if(dccs>3){
for(uint8_t e=0; e<13; e++){
if(dccs<qtfdd[e][0]){
//readoffset
data[(i+(2+aum))] = OSDG(idat_pointer,bit_index,qtfdd[e][1]);
ofsfld += 1;
break;
}
}
}
break;
}
}
}
break;
}
}
}
}
for(uint8_t i=0; i<not_zero_cls_counter; i++){
free(header_cl_symbols[i]);
}
free(header_cl_symbols);
free(CL_cl_lengths);
free(shcs);
free(shcc);
free(used_cls);
free(ll_symbols);
free(ll_cl);
for(uint8_t i=0; i<fsonzl; i++){
free(ll_codes[i]);
}
free(ll_codes);
free(dist_symbols);
free(dist_cl);
for(uint8_t i=0; i<fsonzd; i++){
free(dist_codes[i]);
}
free(dist_codes);
return data;
}
uint16_t lengthAr[29][2] = {
{257,3}, {258,4},
{259,5}, {260,6},
{261,7}, {262,8},
{263,9}, {264,10},
{265,11}, {266,13},
{267,15}, {268,17},
{269,19}, {270,23},
{271,27}, {272,31},
{273,35}, {274,43},
{275,51}, {276,59},
{277,67}, {278,83},
{279,99}, {280,115},
{281,131}, {282,163},
{283,195}, {284,227},
{285,258}
};
uint16_t distanceAr[30][2] = {
{0,1}, {1,2},
{2,3}, {3,4},
{4,5}, {5,7},
{6,9}, {7,13},
{8,17}, {9,25},
{10,33}, {11,49},
{12,65}, {13,97},
{14,129}, {15,193},
{16,257}, {17,385},
{18,513}, {19,769},
{20,1025}, {21,1537},
{22,2049}, {23,3073},
{24,4097}, {25,6145},
{26,8193}, {27,12289},
{28,16385}, {29,24577}
};
uint8_t* Lz77(
uint16_t* lz77_pointer,
uint32_t arbitrary_size
){
//currentindexfordecrypteddata
uint32_t cifdd = 0;
uint8_t* data = (uint8_t*)malloc(arbitrary_size*sizeof(uint8_t));
//lengtharraysizeonvariable
uint16_t lason = (uint16_t)floor((sizeof(lengthAr)/sizeof(lengthAr[0])));
//distancearraysizeonvariable
uint16_t dason = (uint16_t)floor((sizeof(distanceAr)/sizeof(distanceAr[0])));
uint8_t megabreak = 0;
for(uint32_t i=0; i<arbitrary_size; i++){
printf("\ndata at %d: %d",i,lz77_pointer[i]);
if(lz77_pointer[i]==256 || megabreak==1){break;}
if(lz77_pointer[i]>256){
uint32_t rs = 0; //repeatsize
int dtg = 0; //distancetogo
for(uint16_t j=0; j<lason; j++){
if(lz77_pointer[i]==lengthAr[j][0]){
i+=1;
//offsetbitslength
uint16_t obl = 0;
if(lengthAr[j][0]>264 && lengthAr[j][0] != 285){
obl = lz77_pointer[i];
i+=1;
}
rs = (lengthAr[j][1])+obl;
for(uint16_t k=0; k<dason; k++){
if(lz77_pointer[i]==distanceAr[k][0]){
uint16_t obd = 0;
if(distanceAr[k][0]>3){
i+=1;
obd = lz77_pointer[i];
}
dtg = (distanceAr[k][1])+obd;
break;
}
}
break;
}
}
printf("\nLength: %d",rs);
printf("\nDistance: %d",dtg);
int backpos = cifdd-dtg;
if(backpos<0){
printf("\nERROR: Reading negative indexes");
break;
}
for(uint32_t s=0; s<rs; s++){
data[cifdd+s] = data[backpos+s];
}
cifdd+=rs;
}
else{
data[cifdd] = lz77_pointer[i];
cifdd += 1;
}
}
return data;
}
int main(
int nop, //numberofparameters
char** pl //parameterlist
){
uint8_t png[32768];
FILE* fp;
fp = fopen(pl[1],"r");
fread(png,sizeof(uint8_t),32768,fp);
fclose(fp);
uint32_t idatsize = 0;
uint8_t* idatpointer = NULL;
for(uint32_t i=8; i<32768; i++){
uint32_t chunksize = (png[i]<<24)|(png[i+1]<<16)|(png[i+2]<<8)|(png[i+3]);
i += 4;
if(png[i]==73 && png[i+1]==68 && png[i+2]==65 && png[i+3]==84){
idatpointer = (uint8_t*)malloc((chunksize-6)*sizeof(uint8_t));
}
i += 4;
if(idatpointer!=NULL){
for(uint32_t j=0;j<chunksize-4;j++){
idatpointer[j] = png[(i+2)+j];
}
break;
}
i += chunksize;
i += 3;
}
uint32_t imgx = (png[16]<<24)|(png[17]<<16)|(png[18]<<8)|(png[19]);
uint32_t imgy = (png[20]<<24)|(png[21]<<16)|(png[22]<<8)|(png[23]);
uint32_t colortype = png[25];
uint8_t samples_per_pixel = 0;
if(colortype==0){samples_per_pixel=1;}
else if(colortype==2){samples_per_pixel=3;}
else if(colortype==3){samples_per_pixel=1;}
else if(colortype==4){samples_per_pixel=2;}
else if(colortype==6){samples_per_pixel=4;}
uint32_t bit = 0;
uint8_t islastbit = (uint8_t)OSDG(idatpointer,&bit,1);
uint8_t btype = (uint8_t)OSDG(idatpointer,&bit,2);
printf("\nbtype: %d",btype);
uint16_t* lz77_pointer = NULL;
uint32_t arbitrary_size = (((imgx*imgy)*samples_per_pixel)+imgy)+idatsize;
if(btype==0){lz77_pointer = Uncompressed(&bit,idatpointer,arbitrary_size);}
else if(btype==1){lz77_pointer = Static(&bit,idatpointer,arbitrary_size);}
else if(btype==2){lz77_pointer = Dynamic(&bit,idatpointer,arbitrary_size);}
printf("\nLzz7 symbols: ");
for(uint32_t i = 0; i<arbitrary_size; i++){
printf("%d ",lz77_pointer[i]);
}
uint8_t* deencryped_data = Lz77(lz77_pointer,arbitrary_size);
printf("\nDecompressed data: ");
for(uint32_t i = 0; i<arbitrary_size; i++){
printf("%d ",deencryped_data[i]);
}
int8_t c = getchar();
free(deencryped_data);
return 0;
}
Upvotes: 1
Views: 174
Answers (1)
user9706
Reputation:
Here is a minimal fix for the chunk decoder to avoid the buffer overflow:
const uint8_t signature[8] = {137, 'P', 'N', 'G', '\r', '\n', 26, '\n' };
#define CHUNK_LENGTH_LEN 4
#define CHUNK_TYPE_LEN 4
#define CHUNK_CRC_LEN 4
#define COMPRESSION_METHOD_FLAGS_CODE_LEN 1
#define ADDITIONAL_FLAGS_CHECK_BITS_LEN 1
#define CHECK_VALUE_LEN 4
// ...
uint8_t *idatpointer = NULL;
for(uint32_t i=sizeof(signature);;) {
uint32_t chunksize = (png[i]<<24)|(png[i+1]<<16)|(png[i+2]<<8)|(png[i+3]);
i += CHUNK_LENGTH_LEN;
if(!strncmp((char *) png + i, "IDAT", CHUNK_TYPE_LEN)) {
idatpointer = png + i + CHUNK_TYPE_LEN + COMPRESSION_METHOD_FLAGS_CODE_LEN + ADDITIONAL_FLAGS_CHECK_BITS_LEN;
}
if(!strncmp((char *) png + i, "IEND", CHUNK_TYPE_LEN))
break;
i += CHUNK_TYPE_LEN;
i += chunksize;
i += CHUNK_CRC_LEN;
}
Just like the original it does not handle multiple IDAT chunks.
I have been testing with the 10x10 noise image, and it appears to be blocktype 1 (not 2 as indicated in the table).
The result from Static(&bit,idatpointer,arbitrary_size) (you print the same data just as decimal instead of hex):
(gdb) x/55xh lz77_pointer
0x55555555b890: 0x0072 0x011e 0x0011 0x0024 0x0108 0x0002 0x0114 0x0002
0x55555555b8a0: 0x0010 0x0062 0x001b 0x000c 0x0117 0x0000 0x000e 0x0028
0x55555555b8b0: 0x005e 0x0068 0x000b 0x0089 0x00bf 0x00ee 0x011f 0x0019
0x55555555b8c0: 0x004d 0x007a 0x0024 0x00a2 0x0100 0x0000 0x0000 0x0000
0x55555555b8d0: 0x0000 0x0000 0x0000 0x0000 0x0000 0x0000 0x0000 0x0000
0x55555555b8e0: 0x0000 0x0000 0x0000 0x0000 0x0000 0x0000 0x0000 0x0000
0x55555555b8f0: 0x0000 0x0000 0x0000 0x0000 0x0000 0x0000 0x0000
doesn't match the result I get from writing out the 96 bytes of IDAT chunk data to a file then decompressing it with pigz -d < idat.in | xxd:
00000000: 0000 0001 0200 0000 0301 0400 0506 0708 ................
00000010: 0009 0a0b 000c 0003 000d 0e01 0f00 0110 ................
00000020: 1100 0000 0312 1314 1514 030a 0016 1718 ................
00000030: 0300 0000 191a 1b00 0114 1c01 1d1e 031f ................
00000040: 1400 0014 1401 2000 2122 0023 2400 2500 ...... .!".#$.%.
00000050: 2627 0100 0028 0329 0003 2a2b 142c 002d &'...(.)..*+.,.-
00000060: 2e00 2f00 1430 0000 0114 3132 0133 ../..0....12.3
Note that I didn't reverse the filter byte (0x00)1 on each scan line (i.e. remove 10i'th byte). If I did the first 4 bytes would be: 0x00 0x00 0x01 0x02 which clearly doesn't match 0x00 0x72 x01 0x1e.
Looking at the DEFLATE Compressed Data Format Specification version 1.3 those magic numbers look about right for the fixed huffman codes (3.2.6) except the if((nofvfb+256)>264 && (nofvfb+256)<285){ and the if((nofvfb+88)<=287 && (nofvfb+88)>=280 && !ignore){ blocks but I haven't studied it. This should help you a large step forward. I don't know why you need to add those offset before comparing the lit value. If you want to use your own LZ77 implementation I suggest you test it independently. You could also consider using zlib (or other existing implementation instead of writing your at least a stepping stone.
Upvotes: 1
Related Questions
- C - zlib - png crc32/deflate
- Writing uncompress PNG one/first Deflate block OK second things go wrong
- Is DEFLATE used in gzip and png compression the same?
- Custom DEFLATE implementation to speed up PNG encoding
- Why are PNG deflate-block lengths being ignored?
- Deflate test cases
- Trying to understand zlib/deflate in PNG files
- PNG: deflate and zlib
- Incorrect offset for the next block (DEFLATE/PNG)?
- Deflate: uncompressing a PNG without zlib (or any other library)