Skip to content

Instantly share code, notes, and snippets.

@yasar11732
Last active July 14, 2019 18:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save yasar11732/30d2fc9c1c404d776218424e5e3ca795 to your computer and use it in GitHub Desktop.
Save yasar11732/30d2fc9c1c404d776218424e5e3ca795 to your computer and use it in GitHub Desktop.
Canonical Huffman Coding Demo
#include <stddef.h> // NULL
#include <stdint.h>
#include <stdlib.h> // calloc
#include <string.h> // memset
#include <stdio.h>
/*
* Bir kodun en fazla 15 bit olmasına izin vereceğiz.
* Bu nedenle code için 16 bit veri yapısı yeterli.
*/
#ifdef _MSC_VER
__pragma(pack(push, 1))
struct huffmancode {
uint16_t code;
uint8_t len;
};
__pragma(pack(pop))
#elif defined(__GNUC__)
struct __attribute__((packed)) huffmancode {
uint16_t code;
uint8_t len;
};
#endif
// her bir code için uzunluk ve kod değerlerini
// tuttuğumuz array
struct huffmancode tree[0X100];
// her uzunlukta kaç adet kod
// olduğunu saymak için
uint8_t bl_count[0x10];
// her uzunluktaki kodlama için
// atanacak kodu tutar
uint16_t next_code[0x10];
typedef struct _huffman
{
char c;
int freq;
struct _huffman *left;
struct _huffman *right;
} HUFFMANTREE;
typedef struct _huffman_array {
int cap;
int size;
HUFFMANTREE **items;
} HUFFMANARRAY;
HUFFMANTREE *huffmantree_new(char c, int freq)
{
HUFFMANTREE *t = malloc(sizeof(HUFFMANTREE));
t->c = c;
t->freq = freq;
t->left = NULL;
t->right = NULL;
return t;
}
/*
* Selection sort, büyükten küçüğe
*/
void huffman_array_sort(HUFFMANARRAY *arr)
{
int i, k;
int max_index, max_value;
for (i = 0; i < arr->size - 1; i++)
{
max_index = i;
max_value = arr->items[i]->freq;
for (k = i + 1; k < arr->size; k++)
{
if (arr->items[k]->freq > max_value)
{
max_value = arr->items[k]->freq;
max_index = k;
}
}
if (i != max_index)
{
HUFFMANTREE *_tmp = arr->items[i];
arr->items[i] = arr->items[max_index];
arr->items[max_index] = _tmp;
}
}
}
HUFFMANTREE *huffman_array_pop(HUFFMANARRAY *arr)
{
return arr->items[--arr->size];
}
void *huffman_array_add(HUFFMANARRAY *arr, HUFFMANTREE *t)
{
if (arr->size + 1 == arr->cap)
{
arr->cap *= 2;
arr->items = realloc(arr->items, arr->cap * sizeof(HUFFMANTREE *));
}
arr->items[arr->size++] = t;
}
HUFFMANARRAY *huffman_array_new()
{
HUFFMANARRAY *arr = malloc(sizeof(HUFFMANARRAY));
arr->cap = 8;
arr->size = 0;
arr->items = malloc(arr->cap * sizeof(HUFFMANTREE *));
return arr;
}
void huffmantree_print(HUFFMANTREE *t, char *prefix, int size_prefix)
{
if (t->left == NULL && t->right == NULL)
{
prefix[size_prefix] = 0;
printf("%c: %s\n", t->c, prefix);
return;
}
if (t->left)
{
prefix[size_prefix++] = '0';
huffmantree_print(t->left, prefix, size_prefix);
size_prefix--;
}
if (t->right)
{
prefix[size_prefix++] = '1';
huffmantree_print(t->right, prefix, size_prefix);
size_prefix--;
}
}
void load_canonical_codes_from_tree(HUFFMANTREE *t, int length)
{
if (!t)
return;
if (t->c != 0)
{
tree[t->c].len = length;
}
load_canonical_codes_from_tree(t->left, length + 1);
load_canonical_codes_from_tree(t->right, length + 1);
}
char *code_to_binary(struct huffmancode code)
{
char *b = malloc(code.len + 1); // +1 null
int i;
for (i = 0; i < code.len; i++)
{
b[i] = code.code & (1 << (code.len - i - 1)) ? '1' : '0';
}
b[code.len] = 0;
return b;
}
int main(void)
{
unsigned long frequencies[0xFF];
char metin[] = "bu oylesine uzun, oylesine girift bir metin ki, muhakkak gereksiz bitlerini temizlemek gerekir.";
char *pcTemp;
int i;
HUFFMANARRAY *arr = huffman_array_new();
memset(&frequencies[0], 0, sizeof(frequencies));
for (pcTemp = &metin[0]; *pcTemp != 0; pcTemp++)
{
frequencies[(int)*pcTemp]++;
}
for (i = 0; i < 255; i++)
{
if (frequencies[i] > 0)
{
huffman_array_add(arr, huffmantree_new(i, frequencies[i]));
}
}
while (arr->size > 1)
{
huffman_array_sort(arr);
HUFFMANTREE *t1 = huffman_array_pop(arr);
HUFFMANTREE *t2 = huffman_array_pop(arr);
HUFFMANTREE *t3 = calloc(1, sizeof(HUFFMANTREE));
t3->left = t1;
t3->right = t2;
t3->freq = t1->freq + t2->freq;
huffman_array_add(arr, t3);
}
memset(tree, 0, sizeof(tree));
memset(bl_count, 0, sizeof(bl_count));
memset(next_code, 0, sizeof(next_code));
load_canonical_codes_from_tree(huffman_array_pop(arr), 0);
for (i = 0; i < 256; i++)
{
bl_count[tree[i].len]++;
}
int code = 0;
bl_count[0] = 0;
for (i = 1; i < 0x10; i++)
{
code = (code + bl_count[i - 1]) << 1;
next_code[i] = code;
}
for (i = 0; i < 0x100; i++)
{
int len = tree[i].len;
if (len)
{
tree[i].code = next_code[len];
next_code[len]++;
}
}
for (i = 0; i < 0x100; i++)
{
int len = tree[i].len;
if (len)
{
printf("%c: %s\n", i, code_to_binary(tree[i]));
}
}
return 0;
}
@FurkanTheHuman
Copy link

(unsigned long)arr->items[i] ^= (unsigned long)arr->items[max_index];
(unsigned long)arr->items[max_index] ^= (unsigned long)arr->items[i];
(unsigned long)arr->items[i] ^= (unsigned long)arr->items[max_index];

Bu üç satır "error: lvalue required as left operand of assignment" hatası veriyor.

@yasar11732
Copy link
Author

(unsigned long)arr->items[i] ^= (unsigned long)arr->items[max_index];
(unsigned long)arr->items[max_index] ^= (unsigned long)arr->items[i];
(unsigned long)arr->items[i] ^= (unsigned long)arr->items[max_index];

Bu üç satır "error: lvalue required as left operand of assignment" hatası veriyor.

gcc ile derleyip test etmiştim. c++ derleyicisi ile deniyor olabilir misiniz? Syntax açısından bazı farklılıkları olabiliyor.

@FurkanTheHuman
Copy link

Ben de gcc kullandım. Tam olarak "gcc code.c -o output". Gcc version 7.4.0

code.c: In function ‘huffman_array_sort’:
code.c:86:33: error: lvalue required as left operand of assignment
(unsigned long)arr->items[i] ^= (unsigned long)arr->items[max_index];
     ^~

Kodda ^= ifadesini ^~ ile değiştirince derleniyor ama çıktı yanlış gibi.

@yasar11732
Copy link
Author

^= solundaki kısmı tamamen parantez içine alarak deneyebilir misiniz?

@yasar11732
Copy link
Author

Eğer o şekilde de derlenmezse, sorun çıkaran kısmı güncelledim.

@FurkanTheHuman
Copy link

FurkanTheHuman commented Jul 14, 2019

Denedim ama sorun değişmedi. Bu cevabı uyguladım. Çalıştı. Typecasting ile alakalı bir sıkıntı.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment