Ich habe eine Implementierung aus dem LZW Komprimierungs-/Dekomprimierungsalgorithmus und größtenteils zum Quadrat. Ich habe jedoch ein Problem mit einer der Dateien, die ich testen, festgestellt. Im Folgenden ist der Text fürLempel-Ziv-Welch Dekomprimierung nicht existierender Index
Datei sagte#include "bits.h"
int check_endianness(){
int i = 1;
Der Bereich, der meine Implementierung ist rechts von Räumen steckt immer auf die Gruppe vor int i = 1;
Im Folgenden werde ich meine Kompression und Dekompression Schleife jeweils zusammen mit ihrer relativen Debug-Ausgaben aufgenommen haben.
Kompressionsschleife
i=0;
while(i < input_len && ret == LZW_ERR_OK){
//get next byte
char curChar = input_char(f_input, &io_flags);
i++;
//not necessary to check for stream end here since the while condition does that
if(io_flags == STREAM_ERR_READ){
ret = LZW_ERR_READ;
break;
}
seqset(&temp, &curChar, 1);
//add bytes to temp until a sequence is found that is not in lookup
while(i < input_len && dictionary_has_entry(lookup, temp)){
char curChar = input_char(f_input, &io_flags);
i++;
//check for errors/end of file
if(io_flags != STREAM_ERR_OK){
if(io_flags == STREAM_ERR_READ)
ret = LZW_ERR_READ;
break;
}
seqadd(&temp, &curChar, 1);
}
if(temp.length > 1){
#ifdef DEBUG
printf("Adding entry %d: ", lookup->next_value);
for(int j = 0; j < temp.length; j++)
printf("%.4x ", temp.data[j]);
printf("\n");
#endif // DEBUG
dictionary_set_entry(lookup, temp, DICT_SET_FOREVER);
temp.length--; //if temp.length == 1, then the EOF was probably reached
i--; //This is important so that the entire file is read
}
fseek(f_input, -1, SEEK_CUR);
output_short(f_output, dictionary_get_entry_byKey(lookup, temp)->value, STREAM_USE_ENDIAN);
#ifdef DEBUG
printf("Writing code: %d\n", dictionary_get_entry_byKey(lookup, temp)->value);
#endif // DEBUG
}
Kompressions Ausgang
Adding entry 297: 007b 000d
Writing code: 123
Adding entry 298: 000d 000a 0020
Writing code: 273
Adding entry 299: 0020 0020
Writing code: 32
Adding entry 300: 0020 0020 0020
Writing code: 299
Adding entry 301: 0020 0069
Writing code: 32
Adding entry 302: 0069 006e 0074 0020
Dekompression loop
i=0;
while(i < input_len && ret == LZW_ERR_OK){
short code;
entry *e;
code = input_short(f_input, &io_flags, STREAM_USE_ENDIAN);
if(io_flags == STREAM_ERR_READ){
ret = LZW_ERR_READ;
break;
}
i += 2;
//e should never be NULL
printf("Reading code: %d\n", code);
e = dictionary_get_entry_byValue(lookup, code);
assert(e != NULL);
seqset(&temp, e->key.data, e->key.length);
//requires a slightly different approach to the lookup loop in lzw_encode
while(i < input_len && e != NULL){
code = input_short(f_input, &io_flags, STREAM_USE_ENDIAN);
//check for errors/end of file
if(io_flags != STREAM_ERR_OK){
if(io_flags == STREAM_ERR_READ)
ret = LZW_ERR_READ;
break;
}
i += 2;
printf("Reading code: %d\n", code);
//e should never be NULL
e = dictionary_get_entry_byValue(lookup, code);
assert(e != NULL); <------------ This is where it is failing
//start adding bytes to temp
for(size_t j = 0; j < e->key.length; j++){
seqadd(&temp, &e->key.data[j], 1);
if(dictionary_get_entry_byKey(lookup, temp) == NULL){
//sequence not found, add it to dictionary
printf("Adding entry %d: ", lookup->next_value);
dictionary_set_entry(lookup, temp, DICT_SET_FOREVER);
for(int k = 0; k < temp.length; k++)
printf("%.4x ", temp.data[k]);
printf("\n");
e = NULL; //to escape from while
break;
}
}
}
//if more than one code was read go back by two bytes
if(e == NULL){
i -= 2;
fseek(f_input, -2, SEEK_CUR);
}
//only write up to the characters that made a known sequence
temp.length--;
for(size_t j = 0; j < temp.length; j++){
output_char(f_output, temp.data[j]);
#ifdef DEBUG
//printf("%c", temp.data[j]);
#endif // DEBUG
}
}
Dekompression Ausgabe
Reading code: 123
Reading code: 273
Adding entry 297: 007b 000d
Reading code: 273
Reading code: 32
Adding entry 298: 000d 000a 0020
Reading code: 32
Reading code: 299
299, 299 <----error output from dictionary (code asked > next value)
Assertion failed: e != NULL, file lzw.c, line 212
Jede Hilfe sehr geschätzt werden würde.
Danke! Das war eine ziemlich böse Überraschung, als ich es entdeckte. Wenn also ein unbekannter Code gefunden wird, füge ich einfach das erste Zeichen des vorherigen Codes hinzu. – Marcos
Ich erinnere mich nicht an die Details des Updates, aber es ist in der Tat so etwas. – chqrlie