iOS/buildlibs/armv7/allegro-4.4.2/addons/jpgalleg/src/encode.c
/* build_huffman_table:
 *  Builds an optimized huffman table, given the frequency of each value.
 */
Builds an optimized huffman table, given the frequency of each value.
Builds an optimized huffman table given the frequency of each value .
static int
build_huffman_table(HUFFMAN_TABLE *table, unsigned char *num_codes, unsigned char *value)
{
	HUFFMAN_TREE tree;
	HUFFMAN_NODE *node, *new_node, *src_node, *dest_node, *right, *left, *list[17];
	HUFFMAN_ENTRY *entry, *fake_entry = NULL;
	int i, level, max_frequency = 0;
	TRACE("Building new huffman tree");
	tree.head = tree.tail = NULL;
	tree.depth = 0;
	for (i = 0; i < 256; i++)
		max_frequency = MAX(max_frequency, table->entry[i].frequency);
	table->entry[256].frequency = max_frequency - 1;
	table->entry[256].value = -1;
	qsort(table->entry, 257, sizeof(HUFFMAN_ENTRY), compare_entries);
	for (i = 0; i < 257; i++) {
		entry = &table->entry[i];
		if (entry->value < 0)
			fake_entry = entry;
		if (entry->frequency > 0) {
			new_node = (HUFFMAN_NODE *)calloc(1, sizeof(HUFFMAN_NODE));
			new_node->entry = entry;
			new_node->frequency = entry->frequency;
			if (tree.tail) {
				tree.tail->next = new_node;
				new_node->prev = tree.tail;
				tree.tail = new_node;
			}
			else
				tree.head = tree.tail = new_node;
		}
	}
	while (tree.head != tree.tail) {
		new_node = (HUFFMAN_NODE *)calloc(1, sizeof(HUFFMAN_NODE));
		new_node->left = tree.tail;
		new_node->right = tree.tail->prev;
		new_node->frequency = new_node->left->frequency + new_node->right->frequency;
		tree.tail = tree.tail->prev->prev;
		if (tree.tail)
			tree.tail->next = NULL;
		else
			tree.head = NULL;
		for (node = tree.tail; node && (node->frequency < new_node->frequency); node = node->prev)
			;
		if (node) {
			new_node->prev = node;
			new_node->next = node->next;
			if (node->next)
				node->next->prev = new_node;
			else
				tree.tail = new_node;
			node->next = new_node;
		}
		else {
			new_node->next = tree.head;
			new_node->prev = NULL;
			if (tree.head)
				tree.head->prev = new_node;
			else
				tree.tail = new_node;
			tree.head = new_node;
		}
	}
	setup_huffman_tree(&tree, tree.head, 0, NULL);
	while (tree.depth > 16) {
		TRACE("Tree depth > 16; adjusting leaves");
		src_node = find_leaf_at_level(tree.head, tree.depth, 0);
		right = src_node->parent->right;
		left = src_node->parent->left;
		src_node->parent->entry = right->entry;
		src_node->parent->left = src_node->parent->right = NULL;
		level = 2;
		while (!(dest_node = find_leaf_at_level(tree.head, tree.depth - level, 0)))
			level++;
		dest_node->left = left;
		dest_node->right = right;
		right->entry = dest_node->entry;
		dest_node->entry = NULL;
		left->parent = dest_node;
		right->parent = dest_node;
		tree.depth = 0;
		setup_huffman_tree(&tree, tree.head, 0, NULL);
	}
	node = tree.head->right;
	while (!node->entry)
		node = node->right;
	node->parent->right = NULL;
	TRACE("Exchanging rightmost leaf at level %d with fake leaf at level %d%s",
		node->entry->bits_length, fake_entry->bits_length, (node->entry == fake_entry ? "(fake leaf == rightmost leaf)" : ""));
	fake_entry->value = node->entry->value;
	memset(list, 0, 17 * sizeof(HUFFMAN_NODE *));
	setup_huffman_tree(&tree, tree.head, 0, list);
	for (i = 1; i <= 16; i++) {
		num_codes[i] = 0;
		for (node = list[i]; node; node = node->next) {
			*value++ = node->entry->value;
			num_codes[i]++;
		}
	}
	destroy_huffman_tree(tree.head);
	return 0;
}
static int build_huffman_table ( HUFFMAN_TABLE * table , unsigned char * num_codes , unsigned char * value ) { HUFFMAN_TREE tree ; HUFFMAN_NODE * node , * new_node , * src_node , * dest_node , * right , * left , * list [ 17 ] ; HUFFMAN_ENTRY * entry , * fake_entry = NULL ; int i , level , max_frequency = 0 ; TRACE ( " " ) ; tree . head = tree . tail = NULL ; tree . depth = 0 ; for ( i = 0 ; i < 256 ; i ++ ) max_frequency = MAX ( max_frequency , table -> entry [ i ] . frequency ) ; table -> entry [ 256 ] . frequency = max_frequency - 1 ; table -> entry [ 256 ] . value = -1 ; qsort ( table -> entry , 257 , sizeof ( HUFFMAN_ENTRY ) , compare_entries ) ; for ( i = 0 ; i < 257 ; i ++ ) { entry = & table -> entry [ i ] ; if ( entry -> value < 0 ) fake_entry = entry ; if ( entry -> frequency > 0 ) { new_node = ( HUFFMAN_NODE * ) calloc ( 1 , sizeof ( HUFFMAN_NODE ) ) ; new_node -> entry = entry ; new_node -> frequency = entry -> frequency ; if ( tree . tail ) { tree . tail -> next = new_node ; new_node -> prev = tree . tail ; tree . tail = new_node ; } else tree . head = tree . tail = new_node ; } } while ( tree . head != tree . tail ) { new_node = ( HUFFMAN_NODE * ) calloc ( 1 , sizeof ( HUFFMAN_NODE ) ) ; new_node -> left = tree . tail ; new_node -> right = tree . tail -> prev ; new_node -> frequency = new_node -> left -> frequency + new_node -> right -> frequency ; tree . tail = tree . tail -> prev -> prev ; if ( tree . tail ) tree . tail -> next = NULL ; else tree . head = NULL ; for ( node = tree . tail ; node && ( node -> frequency < new_node -> frequency ) ; node = node -> prev ) ; if ( node ) { new_node -> prev = node ; new_node -> next = node -> next ; if ( node -> next ) node -> next -> prev = new_node ; else tree . tail = new_node ; node -> next = new_node ; } else { new_node -> next = tree . head ; new_node -> prev = NULL ; if ( tree . head ) tree . head -> prev = new_node ; else tree . tail = new_node ; tree . head = new_node ; } } setup_huffman_tree ( & tree , tree . head , 0 , NULL ) ; while ( tree . depth > 16 ) { TRACE ( " " ) ; src_node = find_leaf_at_level ( tree . head , tree . depth , 0 ) ; right = src_node -> parent -> right ; left = src_node -> parent -> left ; src_node -> parent -> entry = right -> entry ; src_node -> parent -> left = src_node -> parent -> right = NULL ; level = 2 ; while ( ! ( dest_node = find_leaf_at_level ( tree . head , tree . depth - level , 0 ) ) ) level ++ ; dest_node -> left = left ; dest_node -> right = right ; right -> entry = dest_node -> entry ; dest_node -> entry = NULL ; left -> parent = dest_node ; right -> parent = dest_node ; tree . depth = 0 ; setup_huffman_tree ( & tree , tree . head , 0 , NULL ) ; } node = tree . head -> right ; while ( ! node -> entry ) node = node -> right ; node -> parent -> right = NULL ; TRACE ( " " , node -> entry -> bits_length , fake_entry -> bits_length , ( node -> entry == fake_entry ? " " : " " ) ) ; fake_entry -> value = node -> entry -> value ; memset ( list , 0 , 17 * sizeof ( HUFFMAN_NODE * ) ) ; setup_huffman_tree ( & tree , tree . head , 0 , list ) ; for ( i = 1 ; i <= 16 ; i ++ ) { num_codes [ i ] = 0 ; for ( node = list [ i ] ; node ; node = node -> next ) { * value ++ = node -> entry -> value ; num_codes [ i ] ++ ; } } destroy_huffman_tree ( tree . head ) ; return 0 ; }
build_huffman_table:
  Builds an optimized huffman table, given the frequency of each value.
build_huffman_table : Builds an optimized huffman table given the frequency of each value .
/*
	 *  Adjusts the huffman tree by removing two leaves from a level and
	 *  repositioning them at a lower level. Right leaf replaces the parent tree
	 *  node, left leaf is placed at the first convenient place at lower level.
	 *  This algorithm is used to reposition entries which appear to have a bits
	 *  length higher than 16, which is the maximum allowed by the JPG standard.
	 */ /*
	 *  Find rightmost leaf and replace it with fake entry. This is needed
	 *  as the JPG standard doesn't allow huffman entries with all bits set
	 */ /* Save generated huffman table */