Canonical Huffman Coding Demo

huffman.c

#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;
}

(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.

(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.

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.

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

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

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