Hi,
attached is a patch that ports BablFishPath class to the new list API and the list API is a bit expanded. Further, the algorithm for generating the shortest conversion path is reformulated to be more readable and comprehensible and thoroughly commented. The algorithm for processing the conversion paths is reformulated and commented. The patch also contains minor readability cleanups end speedups.

Regards, Jan

Index: babl/babl-list.c =================================================================== --- babl/babl-list.c (revision 300)
+++ babl/babl-list.c (working copy)
@@ -63,29 +63,78 @@ int
babl_list_size (BablList *list)
{
babl_assert (list);
+
return list->count;
}

-void
-babl_list_insert (BablList *list,
- Babl *item)
+inline void
+babl_list_insert_last (BablList *list, + Babl *item) {
babl_assert(list);
babl_assert(BABL_IS_BABL(item));

if (list->size < list->count + 1) {
- Babl **new_items;
+ Babl **new_items;

- new_items = babl_realloc (list->items, (list->size * 2) * sizeof (BablInstance *)); - babl_assert (new_items);
- list->items = new_items;
- memset (list->items + list->size, 0, list->size * sizeof (BablInstance *)); - list->size *= 2;
+ new_items = babl_realloc (list->items, (list->size * 2) * sizeof (BablInstance *)); + babl_assert (new_items);
+ list->items = new_items;
+ memset (list->items + list->size, 0, list->size * sizeof (BablInstance *)); + list->size *= 2;
}
list->items[list->count++] = item; }

+inline void
+babl_list_remove_last (BablList *list) +{
+ babl_assert (list);
+ babl_assert (list->count > 0);
+
+ list->count--;
+}
+
+inline Babl *
+babl_list_get_first (BablList *list) +{
+ babl_assert (list);
+ babl_assert (list->count > 0);
+
+ return (list->items[0]);
+}
+
+inline Babl *
+babl_list_get_last (BablList *list) +{
+ babl_assert (list);
+ babl_assert (list->count > 0);
+
+ return (list->items[list->count - 1]); +}
+
+inline void
+babl_list_copy (BablList *from,
+ BablList *to)
+{
+ babl_assert (from);
+ babl_assert (to);
+
+ if (to->size < from->count)
+ {
+ Babl **new_items;
+
+ new_items = babl_realloc (to->items, from->count * sizeof (BablInstance *)); + babl_assert (new_items);
+ to->items = new_items;
+ to->size = from->count;
+ }
+
+ memcpy (to->items, from->items, from->count * sizeof (BablInstance *)); + to->count = from->count;
+}
+
void
babl_list_each (BablList *list, BablEachFunction each_fun, Index: babl/babl-list.h
=================================================================== --- babl/babl-list.h (revision 300)
+++ babl/babl-list.h (working copy)
@@ -47,9 +47,22 @@ babl_list_destroy (BablList *list); int
babl_list_size (BablList *list);

-void
-babl_list_insert (BablList *list,
- Babl *item);
+inline void
+babl_list_insert_last (BablList *list, + Babl *item); +
+inline void
+babl_list_remove_last (BablList *list); +
+inline Babl *
+babl_list_get_first (BablList *list); +
+inline Babl *
+babl_list_get_last (BablList *list); +
+inline void
+babl_list_copy (BablList *from,
+ BablList *to);

void
babl_list_each (BablList *list, Index: babl/babl-fish-path.c
=================================================================== --- babl/babl-fish-path.c (revision 300) +++ babl/babl-fish-path.c (working copy) @@ -19,14 +19,35 @@
#include
#include "babl-internal.h"

+#define BABL_LEGAL_ERROR 0.000001 +#define BABL_MAX_COST_VALUE 2000000 +
static double
-chain_error (const Babl *fmt_source, - const Babl *fmt_destination, - BablConversion **chain, - int conversions); +get_conversion_path_error (BablList *path); +
+static long
+process_conversion_path (BablList *path, + void *source_buffer, + void *destination_buffer, + long n); +
+static void
+get_conversion_path (Babl *current_format, + int current_length, + int max_length); +
+static double *
+test_create (void);
+
+static char *
+create_name (const Babl *source,
+ const Babl *destination, + int is_reference); +
+static double legal_error (void);
+
+static int max_path_length (void);

-//#define BABL_LEGAL_ERROR 0.000001 -//#define BABL_LEGAL_ERROR 0.01

static double legal_error (void)
{
@@ -40,7 +61,7 @@ static double legal_error (void) if (env)
error = atof (env);
else
- error = 0.000001;
+ error = BABL_LEGAL_ERROR;
return error;
}

@@ -64,207 +85,99 @@ static int max_path_length (void) return max_length;
}

-typedef struct BablChainContext
-{
- const Babl *from;
- const Babl *to;

- double *best_cost;
- double *best_loss;
- double *best_error;
-
- BablConversion **chain;
- int *conversions;
-
- BablConversion **temp_chain;
- int temp_conversions; -
- int max_conversions;
-} BablChainContext;
-
-static int
-chain_gen_each (Babl *babl,
- void *userdata);
-
-static int
-get_conversion_chain (const Babl *from, - const Babl *to, - double *best_cost, - double *best_loss, - double *best_error, - BablConversion **chain, - int *conversions, - BablConversion **temp_chain, - int temp_conversions, - int max_conversions) +/* The task of BablFishPath construction is to compute + * the shortest path in a graph where formats are the vertices + * and conversions are the edges. However, there is an additional + * constraint to the shortest path, that limits conversion error + * introduced by such a path to be less than BABL_ERROR. This + * prohibits usage of any reasonable shortest path construction + * algorithm such as Dijkstra's algorithm. The shortest path is + * constructed by enumerating all available paths that are less + * than BABL_PATH_LENGTH long, computing their costs and + * conversion errors and backtracking. The backtracking is + * implemented by recursive function get_conversion_path (). + */
+
+static Babl *fish_path;
+static Babl *to_format;
+static BablList *current_path;
+
+static void
+get_conversion_path (Babl *current_format, + int current_length, + int max_length) {
- BablChainContext context;
-
- if (temp_conversions >= max_conversions) - return 0;
-
- if (temp_conversions == 0)
+ if (current_length > max_length) {
- /* chain initialization */
- *conversions = 0;
- *best_cost = 200000.0;
- *best_loss = 200000.0;
- *best_error = 200000.0;
- chain[0] = NULL;
- temp_chain[0] = NULL;
-
- /* Bail out if requesting something stupid (to and from same format, an - * optimized memcpy should be used instead (assuming linear buffers). - */
-
- if (from == to)
- return 0;
+ /* We have reached the maximum recursion + * depth, let's bail out */
+ return;
}
+ else if ((current_length > 0) && (current_format == to_format)) + {
+ /* We have found a candidate path, let's + * see about it's properties */ + double temp_cost = 0.0;
+ double temp_error = 1.0;
+ int i;

- /* copy parameters to stack */
- context.from = from;
- context.to = to;
-
- context.best_cost = best_cost;
- context.best_loss = best_loss;
- context.best_error = best_error; - context.chain = chain;
- context.conversions = conversions; -
- context.temp_chain = temp_chain; - context.temp_conversions = temp_conversions; -
- context.max_conversions = max_conversions; + for (i = 0; i < babl_list_size (current_path); i++) + {
+ temp_error *= (1.0 + babl_conversion_error ((BablConversion *) current_path->items[i])); + temp_cost += babl_conversion_cost ((BablConversion *) current_path->items[i]); + }

- if (temp_conversions == 0)
- {
- temp_chain[temp_conversions] = NULL; - babl_assert (from);
- babl_assert (from->class_type == BABL_FORMAT); - if (!from->format.from_list)
- return 0;
-
- babl_list_each (from->format.from_list, - chain_gen_each, - &context);
+ if (temp_cost < fish_path->fish_path.cost && + temp_error - 1.0 < conversions - 1; i++) + {
+ babl_conversion_process (path->items[i], + aux1_buffer, + aux2_buffer, + n); + /* Swap the auxiliary buffers */ + swap_buffer = aux1_buffer; + aux1_buffer = aux2_buffer; + aux2_buffer = swap_buffer; + }
+
+ /* The last conversion goes from aux1_buffer to destination_buffer */ + babl_conversion_process (babl_list_get_last (path), + aux1_buffer, + destination_buffer, + n);
+
+ /* Free auxiliary buffers */
+ if (aux1_buffer)
+ babl_free (aux1_buffer);
+ if (aux2_buffer)
+ babl_free (aux2_buffer);
+ }
+
+ return n;
+}
+
+#define NUM_TEST_PIXELS (128 + 16 + 16)
static double *
test_create (void)
{
- double *test;
- int i, j;
+ static double test[sizeof (double) * NUM_TEST_PIXELS * 4]; + static int flag = 0;
+ int i, j;
+
+ /* There is no need to generate the test + * more times ... */
+ if (flag)
+ return test;
+ flag = 1;

srandom (20050728);

- test = babl_malloc (sizeof (double) * num_test_pixels * 4); -
/* add 128 pixels in the valid range between 0.0 and 1.0 */ for (i = 0; i < 128 * 4; i++)
test [i] = (double) random () / RAND_MAX; @@ -460,10 +366,7 @@ test_create (void) }

static double
-chain_error (const Babl *fmt_source, - const Babl *fmt_destination, - BablConversion **chain, - int conversions) +get_conversion_path_error (BablList *path) {
Babl *fmt_rgba_double = babl_format_new ( babl_model ("RGBA"),
@@ -476,6 +379,9 @@ chain_error (const Babl *fmt_source
double error = 0.0;

+ Babl *fmt_source = (Babl *) BABL (babl_list_get_first (path))->conversion.source; + Babl *fmt_destination = (Babl *) BABL (babl_list_get_last (path))->conversion.destination; +
double *test;
void *source;
void *destination;
@@ -492,54 +398,53 @@ chain_error (const Babl *fmt_source
test = test_create ();

- source = babl_calloc (num_test_pixels, + source = babl_calloc (NUM_TEST_PIXELS, fmt_source->format.bytes_per_pixel); - destination = babl_calloc (num_test_pixels, + destination = babl_calloc (NUM_TEST_PIXELS, fmt_destination->format.bytes_per_pixel); - ref_destination = babl_calloc (num_test_pixels, + ref_destination = babl_calloc (NUM_TEST_PIXELS, fmt_destination->format.bytes_per_pixel); - destination_rgba_double = babl_calloc (num_test_pixels, + destination_rgba_double = babl_calloc (NUM_TEST_PIXELS, fmt_rgba_double->format.bytes_per_pixel); - ref_destination_rgba_double = babl_calloc (num_test_pixels, + ref_destination_rgba_double = babl_calloc (NUM_TEST_PIXELS, fmt_rgba_double->format.bytes_per_pixel);
/* create sourcebuffer from testbuffer in the correct format */ babl_process (fish_rgba_to_source, - test, source, num_test_pixels); + test, source, NUM_TEST_PIXELS);
/* calculate the reference buffer of how it should be */ babl_process (fish_reference,
- source, ref_destination, num_test_pixels); + source, ref_destination, NUM_TEST_PIXELS);
- /* calculate this chains view of what the result should be */ - chain_process (chain, conversions, source, destination, num_test_pixels); + /* calculate this path's view of what the result should be */ + process_conversion_path (path, source, destination, NUM_TEST_PIXELS);
/* transform the reference and the actual destination buffers to RGBA * for comparison with each other */
babl_process (fish_destination_to_rgba, - ref_destination, ref_destination_rgba_double, num_test_pixels); + ref_destination, ref_destination_rgba_double, NUM_TEST_PIXELS); babl_process (fish_destination_to_rgba, - destination, destination_rgba_double, num_test_pixels); + destination, destination_rgba_double, NUM_TEST_PIXELS);
error = babl_rel_avg_error (destination_rgba_double, ref_destination_rgba_double, - num_test_pixels * 4); + NUM_TEST_PIXELS * 4);
fish_rgba_to_source->fish.processings--; fish_reference->fish.processings--; fish_destination_to_rgba->fish.processings -= 2;
- fish_rgba_to_source->fish.pixels -= num_test_pixels; - fish_reference->fish.pixels -= num_test_pixels; - fish_destination_to_rgba->fish.pixels -= 2 * num_test_pixels; + fish_rgba_to_source->fish.pixels -= NUM_TEST_PIXELS; + fish_reference->fish.pixels -= NUM_TEST_PIXELS; + fish_destination_to_rgba->fish.pixels -= 2 * NUM_TEST_PIXELS;
babl_free (source);
babl_free (destination);
babl_free (destination_rgba_double); babl_free (ref_destination);
babl_free (ref_destination_rgba_double); - babl_free (test);

return error;
}
Index: babl/babl-classes.h
=================================================================== --- babl/babl-classes.h (revision 300) +++ babl/babl-classes.h (working copy) @@ -177,6 +177,8 @@ typedef struct
int planar;
double loss; /*< average relative error when converting from and to RGBA double */ + int visited; /* for convenience in code while searching + for conversion paths */ } BablFormat;

typedef struct
@@ -241,9 +243,7 @@ typedef struct
BablFish fish;
double cost; /* number of ticks *10 + chain_length */ double loss; /* error introduced */ -
- int conversions;
- BablConversion *conversion[BABL_HARD_MAX_PATH_LENGTH]; + BablList *conversion_list; } BablFishPath;

/* BablFishReference
Index: babl/babl-conversion.c
=================================================================== --- babl/babl-conversion.c (revision 300) +++ babl/babl-conversion.c (working copy) @@ -277,7 +277,7 @@ babl_conversion_new (void *first_arg, babl_db_insert (db, babl);
if (!source->type.from_list)
source->type.from_list = babl_list_init_with_size (BABL_CONVERSIONS); - babl_list_insert (source->type.from_list, babl); + babl_list_insert_last (source->type.from_list, babl); return babl;
}

@@ -474,6 +474,11 @@ babl_conversion_error (BablConversion *c if (!conversion)
return 0.0;

+ if (conversion->error != -1.0) /* double conversion against a set value should work */ + {
+ return conversion->error;
+ }
+
fmt_source = BABL (conversion->source); fmt_destination = BABL (conversion->destination);
@@ -496,10 +501,6 @@ babl_conversion_error (BablConversion *c {
conversion->error = 0.000042; }
- if (conversion->error != -1.0) /* double conversion against a set value should work */ - {
- return conversion->error;
- }

test = test_create ();

Index: babl/babl-db.c
=================================================================== --- babl/babl-db.c (revision 300)
+++ babl/babl-db.c (working copy)
@@ -97,7 +97,7 @@ babl_db_insert (BablDb *db, if (item->instance.id)
babl_hash_table_insert (db->id_hash, item); babl_hash_table_insert (db->name_hash, item); - babl_list_insert (db->babl_list, item); + babl_list_insert_last (db->babl_list, item);
/* this point all registered items pass through, a nice * place to brand them with where the item came from. */ Index: babl/babl-fish-stats.c
=================================================================== --- babl/babl-fish-stats.c (revision 300) +++ babl/babl-fish-stats.c (working copy) @@ -48,7 +48,7 @@ table_destination_each (Babl *babl,
fprintf (output_file, "%s", fish->fish.processings > 0 ? " style='background-color: #69f'" : "", - utf8_bar[fish->fish_path.conversions]); + utf8_bar[babl_list_size (fish->fish_path.conversion_list)]);
{
int i;
@@ -68,12 +68,14 @@ table_destination_each (Babl *babl, fprintf (output_file, "error"); fprintf (output_file, "");
- for (i = 0; i < fish->fish_path.conversions; i++) + for (i = 0; i < babl_list_size (fish->fish_path.conversion_list); i++) {
fprintf (output_file, ""); - fprintf (output_file, "%s", BABL (fish->fish_path.conversion[i])->instance.name); - fprintf (output_file, "%li", babl_conversion_cost (&BABL (fish->fish_path.conversion[i])->conversion)); - fprintf (output_file, "%e", babl_conversion_error (&BABL (fish->fish_path.conversion[i])->conversion)); + fprintf (output_file, "%s", BABL (fish->fish_path.conversion_list->items[i])->instance.name); + fprintf (output_file, "%li", + babl_conversion_cost (&BABL (fish->fish_path.conversion_list->items[i])->conversion)); + fprintf (output_file, "%e", + babl_conversion_error (&BABL (fish->fish_path.conversion_list->items[i])->conversion)); fprintf (output_file, ""); }

Index: babl/babl-fish.c
=================================================================== --- babl/babl-fish.c (revision 300)
+++ babl/babl-fish.c (working copy)
@@ -213,6 +213,8 @@ static int
each_babl_fish_destroy (Babl *babl, void *data) {
+ if (babl->class_type == BABL_FISH_PATH) + babl_list_destroy (babl->fish_path.conversion_list); babl_free (babl);
return 0; /* continue iterating */ }
Index: tests/babl_fish_path_fitness.c =================================================================== --- tests/babl_fish_path_fitness.c (revision 300) +++ tests/babl_fish_path_fitness.c (working copy) @@ -43,8 +43,8 @@ static int destination_each (Babl *babl,
if (temp)
{
- printf ("%s", utf8_bar[temp->fish_path.conversions]); - total_length += temp->fish_path.conversions; + printf ("%s", utf8_bar[babl_list_size (temp->fish_path.conversion_list)]); + total_length += babl_list_size (temp->fish_path.conversion_list); total_cost += temp->fish_path.cost; ok++;
total++;