gst/mve/mvevideoenc8.c

   1 /*
   2  * Interplay MVE video encoder (8 bit)
   3  * Copyright (C) 2006 Jens Granseuer <jensgr@gmx.net>
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Library General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2 of the License, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Library General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Library General Public
  16  * License along with this library; if not, write to the
  17  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18  * Boston, MA 02111-1307, USA.
  19  */
  20
  21 #ifdef HAVE_CONFIG_H
  22 #  include "config.h"
  23 #endif
  24
  25 #include <stdlib.h>
  26 #include <string.h>
  27
  28 #include "mve.h"
  29 #include "gstmvemux.h"
  30
  31 typedef struct _GstMveEncoderData GstMveEncoderData;
  32 typedef struct _GstMveEncoding GstMveEncoding;
  33 typedef struct _GstMveApprox GstMveApprox;
  34 typedef struct _GstMveQuant GstMveQuant;
  35
  36 #define MVE_RMASK   0x00ff0000
  37 #define MVE_GMASK   0x0000ff00
  38 #define MVE_BMASK   0x000000ff
  39 #define MVE_RSHIFT  16
  40 #define MVE_GSHIFT  8
  41 #define MVE_BSHIFT  0
  42
  43 #define MVE_RVAL(p)     (((p) & MVE_RMASK) >> MVE_RSHIFT)
  44 #define MVE_GVAL(p)     (((p) & MVE_GMASK) >> MVE_GSHIFT)
  45 #define MVE_BVAL(p)     (((p) & MVE_BMASK) >> MVE_BSHIFT)
  46 #define MVE_COL(r,g,b)  (((r) << MVE_RSHIFT) | ((g) << MVE_GSHIFT) | ((b) << MVE_BSHIFT))
  47
  48 struct _GstMveEncoderData
  49 {
  50   GstMveMux *mve;
  51   /* current position in frame */
  52   guint16 x, y;
  53
  54   /* palette for current frame */
  55   const guint32 *palette;
  56
  57   /* commonly used quantization results
  58      (2 and 4 colors) for the current block */
  59   guint8 q2block[64];
  60   guint8 q2colors[2];
  61   guint32 q2error;
  62   gboolean q2available;
  63
  64   guint8 q4block[64];
  65   guint8 q4colors[4];
  66   guint32 q4error;
  67   gboolean q4available;
  68 };
  69
  70 struct _GstMveEncoding
  71 {
  72   guint8 opcode;
  73   guint8 size;
  74     guint32 (*approx) (GstMveEncoderData * enc, const guint8 * src,
  75       GstMveApprox * res);
  76 };
  77
  78 #define MVE_APPROX_MAX_ERROR  G_MAXUINT32
  79
  80 struct _GstMveApprox
  81 {
  82   guint32 error;
  83   guint8 type;
  84   guint8 data[64];              /* max 64 bytes encoded per block */
  85   guint8 block[64];             /* block in final image */
  86 };
  87
  88 struct _GstMveQuant
  89 {
  90   guint32 col;
  91   guint16 r_total, g_total, b_total;
  92   guint8 r, g, b;
  93   guint8 hits, hits_last;
  94   guint32 max_error;
  95   guint32 max_miss;
  96 };
  97
  98 #define mve_median(mve, src) mve_median_sub ((mve), (src), 8, 8, 0)
  99 #define mve_color_dist(c1, c2) \
 100         mve_color_dist_rgb (MVE_RVAL (c1), MVE_GVAL (c1), MVE_BVAL (c1), \
 101                             MVE_RVAL (c2), MVE_GVAL (c2), MVE_BVAL (c2));
 102 #define mve_color_dist2(c, r, g, b)  \
 103         mve_color_dist_rgb (MVE_RVAL (c), MVE_GVAL (c), MVE_BVAL (c), (r), (g), (b))
 104
 105
 106 /* comparison function for qsort() */
 107 static int
 108 mve_comp_solution (const void *a, const void *b)
 109 {
 110   const GArray *aa = *((GArray **) a);
 111   const GArray *bb = *((GArray **) b);
 112
 113   if (aa->len <= 1)
 114     return G_MAXINT;
 115   else if (bb->len <= 1)
 116     return G_MININT;
 117   else
 118     return g_array_index (aa, GstMveApprox, aa->len - 2).error -
 119         g_array_index (bb, GstMveApprox, bb->len - 2).error;
 120 }
 121
 122 static inline guint32
 123 mve_color_dist_rgb (guint8 r1, guint8 g1, guint8 b1,
 124     guint8 r2, guint8 g2, guint8 b2)
 125 {
 126   /* euclidean distance (minus sqrt) */
 127   gint dr = r1 - r2;
 128   gint dg = g1 - g2;
 129   gint db = b1 - b2;
 130
 131   return dr * dr + dg * dg + db * db;
 132 }
 133
 134 static guint8
 135 mve_find_pal_color (const guint32 * pal, guint32 col)
 136 {
 137   /* find the closest matching color in the palette */
 138   guint i;
 139   guint8 best = 0;
 140   const guint8 r = MVE_RVAL (col), g = MVE_GVAL (col), b = MVE_BVAL (col);
 141   guint32 ebest = MVE_APPROX_MAX_ERROR;
 142
 143   for (i = 0; i < MVE_PALETTE_COUNT; ++i, ++pal) {
 144     guint32 e = mve_color_dist2 (*pal, r, g, b);
 145
 146     if (e < ebest) {
 147       ebest = e;
 148       best = i;
 149
 150       if (ebest == 0)
 151         break;
 152     }
 153   }
 154
 155   return best;
 156 }
 157
 158 static guint8
 159 mve_find_pal_color2 (const guint32 * pal, const guint8 * subset, guint32 col,
 160     guint size)
 161 {
 162   /* find the closest matching color in the partial indexed palette */
 163   guint i;
 164   guint8 best = 0;
 165   const guint8 r = MVE_RVAL (col), g = MVE_GVAL (col), b = MVE_BVAL (col);
 166   guint32 ebest = MVE_APPROX_MAX_ERROR;
 167
 168   for (i = 0; i < size; ++i) {
 169     guint32 e = mve_color_dist2 (pal[subset[i]], r, g, b);
 170
 171     if (e < ebest) {
 172       ebest = e;
 173       best = subset[i];
 174
 175       if (ebest == 0)
 176         break;
 177     }
 178   }
 179
 180   return best;
 181 }
 182
 183 static void
 184 mve_map_to_palette (const GstMveEncoderData * enc, const guint8 * colors,
 185     const guint8 * data, guint8 * dest, guint w, guint h, guint ncols)
 186 {
 187   guint x, y;
 188
 189   for (y = 0; y < h; ++y) {
 190     for (x = 0; x < w; ++x) {
 191       dest[x] =
 192           mve_find_pal_color2 (enc->palette, colors, enc->palette[data[x]],
 193           ncols);
 194     }
 195     data += enc->mve->width;
 196     dest += 8;
 197   }
 198 }
 199
 200 /* compute average color in a sub-block */
 201 static guint8
 202 mve_median_sub (const GstMveEncoderData * enc, const guint8 * src, guint w,
 203     guint h, guint n)
 204 {
 205   guint x, y;
 206   const guint max = w * h, max2 = max >> 1;
 207   guint32 r_total = max2, g_total = max2, b_total = max2;
 208
 209   src += ((n * w) % 8) + (((n * (8 - h)) / (12 - w)) * h * enc->mve->width);
 210
 211   for (y = 0; y < h; ++y) {
 212     for (x = 0; x < w; ++x) {
 213       guint32 p = enc->palette[src[x]];
 214
 215       r_total += MVE_RVAL (p);
 216       g_total += MVE_GVAL (p);
 217       b_total += MVE_BVAL (p);
 218     }
 219     src += enc->mve->width;
 220   }
 221
 222   return mve_find_pal_color (enc->palette,
 223       MVE_COL (r_total / max, g_total / max, b_total / max));
 224 }
 225
 226 static void
 227 mve_quant_init (const GstMveEncoderData * enc, GstMveQuant * q,
 228     guint n_clusters, const guint8 * data, guint w, guint h)
 229 {
 230   guint i;
 231   guint x, y;
 232   guint32 cols[4];
 233   guint16 val[2];
 234
 235   /* init first cluster with lowest (darkest), second with highest (lightest)
 236      color. if we need 4 clusters, fill in first and last color in the block
 237      and hope they make for a good distribution */
 238   cols[0] = cols[1] = cols[2] = enc->palette[data[0]];
 239   cols[3] = enc->palette[data[(h - 1) * enc->mve->width + w - 1]];
 240
 241   /* favour red over green and blue */
 242   val[0] = val[1] =
 243       (MVE_RVAL (cols[0]) << 1) + MVE_GVAL (cols[0]) + MVE_BVAL (cols[0]);
 244
 245   for (y = 0; y < h; ++y) {
 246     for (x = 0; x < w; ++x) {
 247       guint32 c = enc->palette[data[x]];
 248
 249       if ((c != cols[0]) && (c != cols[1])) {
 250         guint v = (MVE_RVAL (c) << 1) + MVE_GVAL (c) + MVE_BVAL (c);
 251
 252         if (v < val[0]) {
 253           val[0] = v;
 254           cols[0] = c;
 255         } else if (v > val[1]) {
 256           val[1] = v;
 257           cols[1] = c;
 258         }
 259       }
 260     }
 261     data += enc->mve->width;
 262   }
 263
 264   for (i = 0; i < n_clusters; ++i) {
 265     q[i].col = cols[i];
 266     q[i].r = MVE_RVAL (cols[i]);
 267     q[i].g = MVE_GVAL (cols[i]);
 268     q[i].b = MVE_BVAL (cols[i]);
 269     q[i].r_total = q[i].g_total = q[i].b_total = 0;
 270     q[i].hits = q[i].hits_last = 0;
 271     q[i].max_error = 0;
 272     q[i].max_miss = 0;
 273   }
 274 }
 275
 276 static gboolean
 277 mve_quant_update_clusters (GstMveQuant * q, guint n_clusters)
 278 {
 279   gboolean changed = FALSE;
 280   guint i;
 281
 282   for (i = 0; i < n_clusters; ++i) {
 283     if (q[i].hits > 0) {
 284       guint32 means = MVE_COL ((q[i].r_total + q[i].hits / 2) / q[i].hits,
 285           (q[i].g_total + q[i].hits / 2) / q[i].hits,
 286           (q[i].b_total + q[i].hits / 2) / q[i].hits);
 287
 288       if ((means != q[i].col) || (q[i].hits != q[i].hits_last))
 289         changed = TRUE;
 290
 291       q[i].col = means;
 292       q[i].r_total = q[i].g_total = q[i].b_total = 0;
 293     } else {
 294       guint j;
 295       guint32 max_err = 0;
 296       GstMveQuant *worst = NULL;
 297
 298       /* try to replace unused cluster with a better representative */
 299       for (j = 0; j < n_clusters; ++j) {
 300         if (q[j].max_error > max_err) {
 301           worst = &q[j];
 302           max_err = worst->max_error;
 303         }
 304       }
 305       if (worst) {
 306         q[i].col = worst->max_miss;
 307         worst->max_error = 0;
 308         changed = TRUE;
 309       }
 310     }
 311
 312     q[i].r = MVE_RVAL (q[i].col);
 313     q[i].g = MVE_GVAL (q[i].col);
 314     q[i].b = MVE_BVAL (q[i].col);
 315     q[i].hits_last = q[i].hits;
 316     q[i].hits = 0;
 317   }
 318   for (i = 0; i < n_clusters; ++i) {
 319     q[i].max_error = 0;
 320   }
 321
 322   return changed;
 323 }
 324
 325 /* quantize a sub-block using a k-means algorithm */
 326 static guint32
 327 mve_quantize (const GstMveEncoderData * enc, const guint8 * src,
 328     guint w, guint h, guint n, guint ncols, guint8 * dest, guint8 * cols)
 329 {
 330   guint x, y, i;
 331   GstMveQuant q[4];
 332   const guint8 *data;
 333   guint32 error;
 334
 335   g_assert (n <= 4 && ncols <= 4);
 336
 337   src += ((n * w) % 8) + (((n * (8 - h)) / (12 - w)) * h * enc->mve->width);
 338   dest += ((n * w) % 8) + (((n * (8 - h)) / (12 - w)) * h * 8);
 339
 340   mve_quant_init (enc, q, ncols, src, w, h);
 341
 342   do {
 343     data = src;
 344     error = 0;
 345
 346     /* for each pixel find the closest cluster */
 347     for (y = 0; y < h; ++y) {
 348       for (x = 0; x < w; ++x) {
 349         guint32 c = enc->palette[data[x]];
 350         guint8 r = MVE_RVAL (c), g = MVE_GVAL (c), b = MVE_BVAL (c);
 351         guint32 minerr = MVE_APPROX_MAX_ERROR, err;
 352         GstMveQuant *best = NULL;
 353
 354         for (i = 0; i < ncols; ++i) {
 355           err = mve_color_dist_rgb (r, g, b, q[i].r, q[i].g, q[i].b);
 356
 357           if (err < minerr) {
 358             minerr = err;
 359             best = &q[i];
 360           }
 361         }
 362
 363         ++best->hits;
 364         best->r_total += r;
 365         best->g_total += g;
 366         best->b_total += b;
 367
 368         if (minerr > best->max_error) {
 369           best->max_error = minerr;
 370           best->max_miss = c;
 371         }
 372
 373         error += minerr;
 374       }
 375       data += enc->mve->width;
 376     }
 377   } while (mve_quant_update_clusters (q, ncols));
 378
 379   /* fill cols array with result colors */
 380   for (i = 0; i < ncols; ++i)
 381     cols[i] = mve_find_pal_color (enc->palette, q[i].col);
 382
 383   /* make sure we have unique colors in slots 0/1 and 2/3 */
 384   if (cols[0] == cols[1])
 385     ++cols[1];
 386   if ((ncols > 2) && (cols[2] == cols[3]))
 387     ++cols[3];
 388
 389   /* generate the resulting quantized block */
 390   mve_map_to_palette (enc, cols, src, dest, w, h, ncols);
 391
 392   return error;
 393 }
 394
 395 static guint32
 396 mve_block_error (const GstMveEncoderData * enc, const guint8 * b1,
 397     const guint8 * b2, guint32 threshold)
 398 {
 399   /* compute error between two blocks in a frame */
 400   guint32 e = 0;
 401   guint x, y;
 402
 403   for (y = 0; y < 8; ++y) {
 404     for (x = 0; x < 8; ++x) {
 405       e += mve_color_dist (enc->palette[*b1], enc->palette[*b2]);
 406
 407       /* using a threshold to return early gives a huge performance bonus */
 408       if (e >= threshold)
 409         return MVE_APPROX_MAX_ERROR;
 410       ++b1;
 411       ++b2;
 412     }
 413
 414     b1 += enc->mve->width - 8;
 415     b2 += enc->mve->width - 8;
 416   }
 417
 418   return e;
 419 }
 420
 421 static guint32
 422 mve_block_error_packed (const GstMveEncoderData * enc, const guint8 * block,
 423     const guint8 * scratch)
 424 {
 425   /* compute error between a block in a frame and a (continuous) scratch pad */
 426   guint32 e = 0;
 427   guint x, y;
 428
 429   for (y = 0; y < 8; ++y) {
 430     for (x = 0; x < 8; ++x) {
 431       guint32 c1 = enc->palette[block[x]], c2 = enc->palette[scratch[x]];
 432
 433       e += mve_color_dist (c1, c2);
 434     }
 435     block += enc->mve->width;
 436     scratch += 8;
 437   }
 438
 439   return e;
 440 }
 441
 442 static void
 443 mve_store_block (const GstMveMux * mve, const guint8 * block, guint8 * scratch)
 444 {
 445   /* copy block from frame to a (continuous) scratch pad */
 446   guint y;
 447
 448   for (y = 0; y < 8; ++y) {
 449     memcpy (scratch, block, 8);
 450     block += mve->width;
 451     scratch += 8;
 452   }
 453 }
 454
 455 static void
 456 mve_restore_block (const GstMveMux * mve, guint8 * block,
 457     const guint8 * scratch)
 458 {
 459   /* copy block from scratch pad to frame */
 460   guint y;
 461
 462   for (y = 0; y < 8; ++y) {
 463     memcpy (block, scratch, 8);
 464     block += mve->width;
 465     scratch += 8;
 466   }
 467 }
 468
 469
 470 static guint32
 471 mve_try_vector (GstMveEncoderData * enc, const guint8 * src,
 472     const guint8 * frame, gint pn, GstMveApprox * apx)
 473 {
 474   /* try to locate a similar 8x8 block in the given frame using a motion vector */
 475   guint i;
 476   gint dx, dy;
 477   gint fx, fy;
 478   guint32 err;
 479
 480   apx->error = MVE_APPROX_MAX_ERROR;
 481
 482   for (i = 0; i < 256; ++i) {
 483     if (i < 56) {
 484       dx = 8 + (i % 7);
 485       dy = i / 7;
 486     } else {
 487       dx = -14 + ((i - 56) % 29);
 488       dy = 8 + ((i - 56) / 29);
 489     }
 490
 491     fx = enc->x + dx * pn;
 492     fy = enc->y + dy * pn;
 493
 494     if ((fx >= 0) && (fy >= 0) && (fx + 8 <= enc->mve->width)
 495         && (fy + 8 <= enc->mve->height)) {
 496       err =
 497           mve_block_error (enc, src, frame + fy * enc->mve->width + fx,
 498           apx->error);
 499       if (err < apx->error) {
 500         apx->data[0] = i;
 501         mve_store_block (enc->mve, frame + fy * enc->mve->width + fx,
 502             apx->block);
 503         apx->error = err;
 504         if (err == 0)
 505           return 0;
 506       }
 507     }
 508   }
 509
 510   return apx->error;
 511 }
 512
 513 static guint32
 514 mve_encode_0x0 (GstMveEncoderData * enc, const guint8 * src, GstMveApprox * apx)
 515 {
 516   /* copy a block from the last frame (0 bytes) */
 517   if (enc->mve->last_frame == NULL)
 518     return MVE_APPROX_MAX_ERROR;
 519
 520   mve_store_block (enc->mve,
 521       GST_BUFFER_DATA (enc->mve->last_frame) +
 522       enc->y * enc->mve->width + enc->x, apx->block);
 523   apx->error = mve_block_error_packed (enc, src, apx->block);
 524   return apx->error;
 525 }
 526
 527 static guint32
 528 mve_encode_0x1 (GstMveEncoderData * enc, const guint8 * src, GstMveApprox * apx)
 529 {
 530   /* copy a block from the second to last frame (0 bytes) */
 531   if (enc->mve->second_last_frame == NULL)
 532     return MVE_APPROX_MAX_ERROR;
 533
 534   mve_store_block (enc->mve,
 535       GST_BUFFER_DATA (enc->mve->second_last_frame) +
 536       enc->y * enc->mve->width + enc->x, apx->block);
 537   apx->error = mve_block_error_packed (enc, src, apx->block);
 538   return apx->error;
 539 }
 540
 541 static guint32
 542 mve_encode_0x2 (GstMveEncoderData * enc, const guint8 * src, GstMveApprox * apx)
 543 {
 544   /* copy block from 2 frames ago using a motion vector (1 byte) */
 545   if (enc->mve->quick_encoding || enc->mve->second_last_frame == NULL)
 546     return MVE_APPROX_MAX_ERROR;
 547
 548   apx->error = mve_try_vector (enc, src,
 549       GST_BUFFER_DATA (enc->mve->second_last_frame), 1, apx);
 550   return apx->error;
 551 }
 552
 553 static guint32
 554 mve_encode_0x3 (GstMveEncoderData * enc, const guint8 * src, GstMveApprox * apx)
 555 {
 556   /* copy 8x8 block from current frame from an up/left block (1 byte) */
 557   if (enc->mve->quick_encoding)
 558     return MVE_APPROX_MAX_ERROR;
 559
 560   apx->error = mve_try_vector (enc, src,
 561       src - enc->mve->width * enc->y - enc->x, -1, apx);
 562   return apx->error;
 563 }
 564
 565
 566 static guint32
 567 mve_encode_0x4 (GstMveEncoderData * enc, const guint8 * src, GstMveApprox * apx)
 568 {
 569   /* copy a block from previous frame using a motion vector (-8/-8 to +7/+7) (1 byte) */
 570   const GstMveMux *mve = enc->mve;
 571   guint32 err;
 572   const guint8 *frame;
 573   gint x1, x2, xi, y1, y2, yi;
 574
 575   if (mve->last_frame == NULL)
 576     return MVE_APPROX_MAX_ERROR;
 577
 578   frame = GST_BUFFER_DATA (mve->last_frame);
 579
 580   x1 = enc->x - 8;
 581   x2 = enc->x + 7;
 582   if (x1 < 0)
 583     x1 = 0;
 584   else if (x2 + 8 > mve->width)
 585     x2 = mve->width - 8;
 586
 587   y1 = enc->y - 8;
 588   y2 = enc->y + 7;
 589   if (y1 < 0)
 590     y1 = 0;
 591   else if (y2 + 8 > mve->height)
 592     y2 = mve->height - 8;
 593
 594   apx->error = MVE_APPROX_MAX_ERROR;
 595
 596   for (yi = y1; yi <= y2; ++yi) {
 597     guint yoff = yi * mve->width;
 598
 599     for (xi = x1; xi <= x2; ++xi) {
 600       err = mve_block_error (enc, src, frame + yoff + xi, apx->error);
 601       if (err < apx->error) {
 602         apx->data[0] = ((xi - enc->x + 8) & 0xF) | ((yi - enc->y + 8) << 4);
 603         mve_store_block (mve, frame + yoff + xi, apx->block);
 604         apx->error = err;
 605         if (err == 0)
 606           return 0;
 607       }
 608     }
 609   }
 610
 611   return apx->error;
 612 }
 613
 614 static guint32
 615 mve_encode_0x5 (GstMveEncoderData * enc, const guint8 * src, GstMveApprox * apx)
 616 {
 617   /* copy a block from previous frame using a motion vector
 618      (-128/-128 to +127/+127) (2 bytes) */
 619   const GstMveMux *mve = enc->mve;
 620   guint32 err;
 621   const guint8 *frame;
 622   gint x1, x2, xi, y1, y2, yi;
 623
 624   if (mve->quick_encoding || mve->last_frame == NULL)
 625     return MVE_APPROX_MAX_ERROR;
 626
 627   frame = GST_BUFFER_DATA (mve->last_frame);
 628
 629   x1 = enc->x - 128;
 630   x2 = enc->x + 127;
 631   if (x1 < 0)
 632     x1 = 0;
 633   if (x2 + 8 > mve->width)
 634     x2 = mve->width - 8;
 635
 636   y1 = enc->y - 128;
 637   y2 = enc->y + 127;
 638   if (y1 < 0)
 639     y1 = 0;
 640   if (y2 + 8 > mve->height)
 641     y2 = mve->height - 8;
 642
 643   apx->error = MVE_APPROX_MAX_ERROR;
 644
 645   for (yi = y1; yi <= y2; ++yi) {
 646     gint yoff = yi * mve->width;
 647
 648     for (xi = x1; xi <= x2; ++xi) {
 649       err = mve_block_error (enc, src, frame + yoff + xi, apx->error);
 650       if (err < apx->error) {
 651         apx->data[0] = xi - enc->x;
 652         apx->data[1] = yi - enc->y;
 653         mve_store_block (mve, frame + yoff + xi, apx->block);
 654         apx->error = err;
 655         if (err == 0)
 656           return 0;
 657       }
 658     }
 659   }
 660
 661   return apx->error;
 662 }
 663
 664 static guint32
 665 mve_encode_0x7a (GstMveEncoderData * enc, const guint8 * src,
 666     GstMveApprox * apx)
 667 {
 668   /* 2-color encoding for 2x2 solid blocks (4 bytes) */
 669   guint32 pix[4];
 670   guint8 mean;
 671   guint32 e1, e2;
 672   guint x, y;
 673   guint8 r[2], g[2], b[2], rb, gb, bb;
 674   guint8 *block = apx->block;
 675   guint16 mask = 0x0001;
 676   guint16 flags = 0;
 677
 678   /* calculate mean colors for the entire block */
 679   if (!enc->q2available) {
 680     enc->q2error =
 681         mve_quantize (enc, src, 8, 8, 0, 2, enc->q2block, enc->q2colors);
 682     enc->q2available = TRUE;
 683   }
 684
 685   /* p0 > p1 */
 686   apx->data[0] = MAX (enc->q2colors[0], enc->q2colors[1]);
 687   apx->data[1] = MIN (enc->q2colors[0], enc->q2colors[1]);
 688
 689   for (x = 0; x < 2; ++x) {
 690     r[x] = MVE_RVAL (enc->palette[apx->data[x]]);
 691     g[x] = MVE_GVAL (enc->palette[apx->data[x]]);
 692     b[x] = MVE_BVAL (enc->palette[apx->data[x]]);
 693   }
 694
 695   /* calculate mean colors for each 2x2 block and map to global colors */
 696   for (y = 0; y < 4; ++y) {
 697     for (x = 0; x < 4; ++x, mask <<= 1) {
 698       pix[0] = enc->palette[src[0]];
 699       pix[1] = enc->palette[src[1]];
 700       pix[2] = enc->palette[src[enc->mve->width]];
 701       pix[3] = enc->palette[src[enc->mve->width + 1]];
 702
 703       rb = (MVE_RVAL (pix[0]) + MVE_RVAL (pix[1]) + MVE_RVAL (pix[2]) +
 704           MVE_RVAL (pix[3]) + 2) / 4;
 705       gb = (MVE_GVAL (pix[0]) + MVE_GVAL (pix[1]) + MVE_GVAL (pix[2]) +
 706           MVE_GVAL (pix[3]) + 2) / 4;
 707       bb = (MVE_BVAL (pix[0]) + MVE_BVAL (pix[1]) + MVE_BVAL (pix[2]) +
 708           MVE_BVAL (pix[3]) + 2) / 4;
 709
 710       e1 = mve_color_dist_rgb (rb, gb, bb, r[0], g[0], b[0]);
 711       e2 = mve_color_dist_rgb (rb, gb, bb, r[1], g[1], b[1]);
 712
 713       if (e1 > e2) {
 714         mean = apx->data[1];
 715         flags |= mask;
 716       } else {
 717         mean = apx->data[0];
 718       }
 719
 720       block[0] = block[1] = block[8] = block[9] = mean;
 721
 722       src += 2;
 723       block += 2;
 724     }
 725     src += (enc->mve->width * 2) - 8;
 726     block += 8;
 727   }
 728
 729   apx->data[2] = flags & 0x00FF;
 730   apx->data[3] = (flags & 0xFF00) >> 8;
 731
 732   apx->error =
 733       mve_block_error_packed (enc, src - enc->mve->width * 8, apx->block);
 734   return apx->error;
 735 }
 736
 737 static guint32
 738 mve_encode_0x7b (GstMveEncoderData * enc, const guint8 * src,
 739     GstMveApprox * apx)
 740 {
 741   /* generic 2-color encoding (10 bytes) */
 742   guint x, y;
 743   guint8 *data = apx->data;
 744   guint8 *block = apx->block;
 745
 746   if (!enc->q2available) {
 747     enc->q2error =
 748         mve_quantize (enc, src, 8, 8, 0, 2, enc->q2block, enc->q2colors);
 749     enc->q2available = TRUE;
 750   }
 751
 752   memcpy (block, enc->q2block, 64);
 753
 754   /* p0 <= p1 */
 755   data[0] = MIN (enc->q2colors[0], enc->q2colors[1]);
 756   data[1] = MAX (enc->q2colors[0], enc->q2colors[1]);
 757   data += 2;
 758
 759   for (y = 0; y < 8; ++y) {
 760     guint8 flags = 0;
 761
 762     for (x = 0x01; x <= 0x80; x <<= 1) {
 763       if (*block == apx->data[1])
 764         flags |= x;
 765       ++block;
 766     }
 767     *data++ = flags;
 768   }
 769
 770   apx->error = enc->q2error;
 771   return apx->error;
 772 }
 773
 774 static guint32
 775 mve_encode_0x8a (GstMveEncoderData * enc, const guint8 * src,
 776     GstMveApprox * apx)
 777 {
 778   /* 2-color encoding for top and bottom half (12 bytes) */
 779   guint8 cols[2];
 780   guint32 flags;
 781   guint i, x, y, shifter;
 782   guint8 *block = apx->block;
 783   guint8 *data = apx->data;
 784
 785   apx->error = 0;
 786
 787   for (i = 0; i < 2; ++i) {
 788     apx->error += mve_quantize (enc, src, 8, 4, i, 2, apx->block, cols);
 789
 790     flags = 0;
 791     shifter = 0;
 792
 793     /* p0 > p1 && p2 > p3 */
 794     data[0] = MAX (cols[0], cols[1]);
 795     data[1] = MIN (cols[0], cols[1]);
 796
 797     for (y = 0; y < 4; ++y) {
 798       for (x = 0; x < 8; ++x, ++shifter) {
 799         if (block[x] == data[1])
 800           flags |= 1 << shifter;
 801       }
 802       block += 8;
 803     }
 804     data[2] = flags & 0x000000FF;
 805     data[3] = (flags & 0x0000FF00) >> 8;
 806     data[4] = (flags & 0x00FF0000) >> 16;
 807     data[5] = (flags & 0xFF000000) >> 24;
 808     data += 6;
 809   }
 810
 811   return apx->error;
 812 }
 813
 814 static guint32
 815 mve_encode_0x8b (GstMveEncoderData * enc, const guint8 * src,
 816     GstMveApprox * apx)
 817 {
 818   /* 2-color encoding for left and right half (12 bytes) */
 819   guint8 cols[2];
 820   guint32 flags;
 821   guint i, x, y, shifter;
 822   guint8 *block = apx->block;
 823   guint8 *data = apx->data;
 824
 825   apx->error = 0;
 826
 827   for (i = 0; i < 2; ++i) {
 828     apx->error += mve_quantize (enc, src, 4, 8, i, 2, apx->block, cols);
 829
 830     flags = 0;
 831     shifter = 0;
 832
 833     /* p0 > p1 && p2 <= p3 */
 834     data[i] = MAX (cols[0], cols[1]);
 835     data[i ^ 1] = MIN (cols[0], cols[1]);
 836
 837     for (y = 0; y < 8; ++y) {
 838       for (x = 0; x < 4; ++x, ++shifter) {
 839         if (block[x] == data[1])
 840           flags |= 1 << shifter;
 841       }
 842       block += 8;
 843     }
 844
 845     data[2] = flags & 0x000000FF;
 846     data[3] = (flags & 0x0000FF00) >> 8;
 847     data[4] = (flags & 0x00FF0000) >> 16;
 848     data[5] = (flags & 0xFF000000) >> 24;
 849     data += 6;
 850     block = apx->block + 4;
 851   }
 852
 853   return apx->error;
 854 }
 855
 856 static guint32
 857 mve_encode_0x8c (GstMveEncoderData * enc, const guint8 * src,
 858     GstMveApprox * apx)
 859 {
 860   /* 2-color encoding for each 4x4 quadrant (16 bytes) */
 861   guint8 cols[2];
 862   guint16 flags;
 863   guint i, x, y, shifter;
 864   guint8 *block;
 865   guint8 *data = apx->data;
 866
 867   apx->error = 0;
 868
 869   for (i = 0; i < 4; ++i) {
 870     apx->error +=
 871         mve_quantize (enc, src, 4, 4, ((i & 1) << 1) | ((i & 2) >> 1), 2,
 872         apx->block, cols);
 873
 874     /* p0 < p1 */
 875     if (i == 0) {
 876       data[0] = MIN (cols[0], cols[1]);
 877       data[1] = MAX (cols[0], cols[1]);
 878     } else {
 879       data[0] = cols[0];
 880       data[1] = cols[1];
 881     }
 882
 883     block = apx->block + ((i / 2) * 4) + ((i % 2) * 32);
 884     flags = 0;
 885     shifter = 0;
 886
 887     for (y = 0; y < 4; ++y) {
 888       for (x = 0; x < 4; ++x, ++shifter) {
 889         if (block[x] == data[1])
 890           flags |= 1 << shifter;
 891       }
 892       block += 8;
 893     }
 894
 895     data[2] = flags & 0x00FF;
 896     data[3] = (flags & 0xFF00) >> 8;
 897     data += 4;
 898   }
 899
 900   return apx->error;
 901 }
 902
 903 static guint32
 904 mve_encode_0x9a (GstMveEncoderData * enc, const guint8 * src,
 905     GstMveApprox * apx)
 906 {
 907   /* 4-color encoding for 2x2 solid blocks (8 bytes) */
 908   guint32 p[4];
 909   guint32 e, emin;
 910   guint i, x, y, mean = 0;
 911   guint8 r[4], g[4], b[4], rb, gb, bb;
 912   guint8 *block = apx->block;
 913   guint shifter = 0;
 914   guint32 flags = 0;
 915
 916   /* calculate mean colors for the entire block */
 917   if (!enc->q4available) {
 918     enc->q4error =
 919         mve_quantize (enc, src, 8, 8, 0, 4, enc->q4block, enc->q4colors);
 920     enc->q4available = TRUE;
 921   }
 922
 923   /* p0 <= p1 && p2 > p3 */
 924   apx->data[0] = MIN (enc->q4colors[0], enc->q4colors[1]);
 925   apx->data[1] = MAX (enc->q4colors[0], enc->q4colors[1]);
 926   apx->data[2] = MAX (enc->q4colors[2], enc->q4colors[3]);
 927   apx->data[3] = MIN (enc->q4colors[2], enc->q4colors[3]);
 928
 929   for (i = 0; i < 4; ++i) {
 930     r[i] = MVE_RVAL (enc->palette[apx->data[i]]);
 931     g[i] = MVE_GVAL (enc->palette[apx->data[i]]);
 932     b[i] = MVE_BVAL (enc->palette[apx->data[i]]);
 933   }
 934
 935   /* calculate mean colors for each 2x2 block and map to global colors */
 936   for (y = 0; y < 4; ++y) {
 937     for (x = 0; x < 4; ++x, shifter += 2) {
 938       p[0] = enc->palette[src[0]];
 939       p[1] = enc->palette[src[1]];
 940       p[2] = enc->palette[src[enc->mve->width]];
 941       p[3] = enc->palette[src[enc->mve->width + 1]];
 942
 943       rb = (MVE_RVAL (p[0]) + MVE_RVAL (p[1]) + MVE_RVAL (p[2]) +
 944           MVE_RVAL (p[3]) + 2) / 4;
 945       gb = (MVE_GVAL (p[0]) + MVE_GVAL (p[1]) + MVE_GVAL (p[2]) +
 946           MVE_GVAL (p[3]) + 2) / 4;
 947       bb = (MVE_BVAL (p[0]) + MVE_BVAL (p[1]) + MVE_BVAL (p[2]) +
 948           MVE_BVAL (p[3]) + 2) / 4;
 949
 950       emin = MVE_APPROX_MAX_ERROR;
 951       for (i = 0; i < 4; ++i) {
 952         e = mve_color_dist_rgb (rb, gb, bb, r[i], g[i], b[i]);
 953         if (e < emin) {
 954           emin = e;
 955           mean = i;
 956         }
 957       }
 958
 959       flags |= mean << shifter;
 960       block[0] = block[1] = block[8] = block[9] = apx->data[mean];
 961
 962       src += 2;
 963       block += 2;
 964     }
 965     src += (enc->mve->width * 2) - 8;
 966     block += 8;
 967   }
 968
 969   apx->data[4] = flags & 0x000000FF;
 970   apx->data[5] = (flags & 0x0000FF00) >> 8;
 971   apx->data[6] = (flags & 0x00FF0000) >> 16;
 972   apx->data[7] = (flags & 0xFF000000) >> 24;
 973
 974   apx->error =
 975       mve_block_error_packed (enc, src - 8 * enc->mve->width, apx->block);
 976   return apx->error;
 977 }
 978
 979 static guint32
 980 mve_encode_0x9b (GstMveEncoderData * enc, const guint8 * src,
 981     GstMveApprox * apx)
 982 {
 983   /* 4-color encoding for 2x1 solid blocks (12 bytes) */
 984   guint32 p[2];
 985   guint32 e, emin;
 986   guint i, x, y, mean = 0;
 987   guint8 r[4], g[4], b[4], rb, gb, bb;
 988   guint8 *data = apx->data;
 989   guint8 *block = apx->block;
 990   guint shifter = 0;
 991   guint32 flags = 0;
 992
 993   /* calculate mean colors for the entire block */
 994   if (!enc->q4available) {
 995     enc->q4error =
 996         mve_quantize (enc, src, 8, 8, 0, 4, enc->q4block, enc->q4colors);
 997     enc->q4available = TRUE;
 998   }
 999
1000   /* p0 > p1 && p2 <= p3 */
1001   data[0] = MAX (enc->q4colors[0], enc->q4colors[1]);
1002   data[1] = MIN (enc->q4colors[0], enc->q4colors[1]);
1003   data[2] = MIN (enc->q4colors[2], enc->q4colors[3]);
1004   data[3] = MAX (enc->q4colors[2], enc->q4colors[3]);
1005
1006   for (i = 0; i < 4; ++i) {
1007     r[i] = MVE_RVAL (enc->palette[data[i]]);
1008     g[i] = MVE_GVAL (enc->palette[data[i]]);
1009     b[i] = MVE_BVAL (enc->palette[data[i]]);
1010   }
1011   data += 4;
1012
1013   /* calculate mean colors for each 2x1 block and map to global colors */
1014   for (y = 0; y < 8; ++y) {
1015     for (x = 0; x < 4; ++x, shifter += 2) {
1016       p[0] = enc->palette[src[0]];
1017       p[1] = enc->palette[src[1]];
1018       rb = (MVE_RVAL (p[0]) + MVE_RVAL (p[1]) + 1) / 2;
1019       gb = (MVE_GVAL (p[0]) + MVE_GVAL (p[1]) + 1) / 2;
1020       bb = (MVE_BVAL (p[0]) + MVE_BVAL (p[1]) + 1) / 2;
1021
1022       emin = MVE_APPROX_MAX_ERROR;
1023       for (i = 0; i < 4; ++i) {
1024         e = mve_color_dist_rgb (rb, gb, bb, r[i], g[i], b[i]);
1025         if (e < emin) {
1026           emin = e;
1027           mean = i;
1028         }
1029       }
1030
1031       flags |= mean << shifter;
1032       block[0] = block[1] = apx->data[mean];
1033
1034       src += 2;
1035       block += 2;
1036     }
1037
1038     if ((y == 3) || (y == 7)) {
1039       data[0] = flags & 0x000000FF;
1040       data[1] = (flags & 0x0000FF00) >> 8;
1041       data[2] = (flags & 0x00FF0000) >> 16;
1042       data[3] = (flags & 0xFF000000) >> 24;
1043       data += 4;
1044
1045       flags = 0;
1046       shifter = 0;
1047     }
1048
1049     src += enc->mve->width - 8;
1050   }
1051
1052   apx->error =
1053       mve_block_error_packed (enc, src - 8 * enc->mve->width, apx->block);
1054   return apx->error;
1055 }
1056
1057 static guint32
1058 mve_encode_0x9c (GstMveEncoderData * enc, const guint8 * src,
1059     GstMveApprox * apx)
1060 {
1061   /* 4-color encoding for 1x2 solid blocks (12 bytes) */
1062   guint32 p[2];
1063   guint32 e, emin;
1064   guint i, x, y, mean = 0;
1065   guint8 r[4], g[4], b[4], rb, gb, bb;
1066   guint8 *data = apx->data;
1067   guint8 *block = apx->block;
1068   guint shifter = 0;
1069   guint32 flags = 0;
1070
1071   /* calculate mean colors for the entire block */
1072   if (!enc->q4available) {
1073     enc->q4error =
1074         mve_quantize (enc, src, 8, 8, 0, 4, enc->q4block, enc->q4colors);
1075     enc->q4available = TRUE;
1076   }
1077
1078   /* p0 > p1 && p2 > p3 */
1079   data[0] = MAX (enc->q4colors[0], enc->q4colors[1]);
1080   data[1] = MIN (enc->q4colors[0], enc->q4colors[1]);
1081   data[2] = MAX (enc->q4colors[2], enc->q4colors[3]);
1082   data[3] = MIN (enc->q4colors[2], enc->q4colors[3]);
1083
1084   for (i = 0; i < 4; ++i) {
1085     r[i] = MVE_RVAL (enc->palette[data[i]]);
1086     g[i] = MVE_GVAL (enc->palette[data[i]]);
1087     b[i] = MVE_BVAL (enc->palette[data[i]]);
1088   }
1089   data += 4;
1090
1091   /* calculate mean colors for each 1x2 block and map to global colors */
1092   for (y = 0; y < 4; ++y) {
1093     for (x = 0; x < 8; ++x, shifter += 2) {
1094       p[0] = enc->palette[src[0]];
1095       p[1] = enc->palette[src[enc->mve->width]];
1096       rb = (MVE_RVAL (p[0]) + MVE_RVAL (p[1]) + 1) / 2;
1097       gb = (MVE_GVAL (p[0]) + MVE_GVAL (p[1]) + 1) / 2;
1098       bb = (MVE_BVAL (p[0]) + MVE_BVAL (p[1]) + 1) / 2;
1099
1100       emin = MVE_APPROX_MAX_ERROR;
1101       for (i = 0; i < 4; ++i) {
1102         e = mve_color_dist_rgb (rb, gb, bb, r[i], g[i], b[i]);
1103         if (e < emin) {
1104           emin = e;
1105           mean = i;
1106         }
1107       }
1108
1109       flags |= mean << shifter;
1110       block[0] = block[8] = apx->data[mean];
1111
1112       ++src;
1113       ++block;
1114     }
1115
1116     if ((y == 1) || (y == 3)) {
1117       data[0] = flags & 0x000000FF;
1118       data[1] = (flags & 0x0000FF00) >> 8;
1119       data[2] = (flags & 0x00FF0000) >> 16;
1120       data[3] = (flags & 0xFF000000) >> 24;
1121       data += 4;
1122
1123       flags = 0;
1124       shifter = 0;
1125     }
1126
1127     src += (enc->mve->width * 2) - 8;
1128     block += 8;
1129   }
1130
1131   apx->error =
1132       mve_block_error_packed (enc, src - 8 * enc->mve->width, apx->block);
1133   return apx->error;
1134 }
1135
1136 static guint32
1137 mve_encode_0x9d (GstMveEncoderData * enc, const guint8 * src,
1138     GstMveApprox * apx)
1139 {
1140   /* generic 4-color encoding (20 bytes) */
1141   guint32 flags = 0;
1142   guint shifter = 0;
1143   guint i, x, y;
1144   guint8 *data = apx->data;
1145   guint8 *block = apx->block;
1146
1147   if (!enc->q4available) {
1148     enc->q4error =
1149         mve_quantize (enc, src, 8, 8, 0, 4, enc->q4block, enc->q4colors);
1150     enc->q4available = TRUE;
1151   }
1152
1153   memcpy (block, enc->q4block, 64);
1154
1155   /* p0 <= p1 && p2 <= p3 */
1156   data[0] = MIN (enc->q4colors[0], enc->q4colors[1]);
1157   data[1] = MAX (enc->q4colors[0], enc->q4colors[1]);
1158   data[2] = MIN (enc->q4colors[2], enc->q4colors[3]);
1159   data[3] = MAX (enc->q4colors[2], enc->q4colors[3]);
1160   data += 4;
1161
1162   for (y = 0; y < 8; ++y) {
1163     for (x = 0; x < 8; ++x, shifter += 2) {
1164
1165       for (i = 0; i < 3; ++i) {
1166         if (*block == apx->data[i])
1167           break;
1168       }
1169
1170       flags |= i << shifter;
1171       ++block;
1172     }
1173
1174     data[0] = flags & 0x000000FF;
1175     data[1] = (flags & 0x0000FF00) >> 8;
1176     data += 2;
1177     shifter = 0;
1178     flags = 0;
1179   }
1180
1181   apx->error = enc->q4error;
1182   return apx->error;
1183 }
1184
1185 static guint32
1186 mve_encode_0xaa (GstMveEncoderData * enc, const guint8 * src,
1187     GstMveApprox * apx)
1188 {
1189   /* 4-color encoding for top and bottom half (24 bytes) */
1190   guint8 cols[4];
1191   guint32 flags;
1192   guint i, j, x, y, shifter;
1193   guint8 *block = apx->block;
1194   guint8 *data = apx->data;
1195   const guint8 *p;
1196
1197   apx->error = 0;
1198
1199   for (i = 0; i < 2; ++i) {
1200     apx->error += mve_quantize (enc, src, 8, 4, i, 4, apx->block, cols);
1201
1202     flags = 0;
1203     shifter = 0;
1204
1205     /* p0 > p1 && p4 > p5 */
1206     data[0] = MAX (cols[0], cols[1]);
1207     data[1] = MIN (cols[0], cols[1]);
1208     data[2] = cols[2];
1209     data[3] = cols[3];
1210     p = data;
1211     data += 4;
1212
1213     for (y = 0; y < 4; ++y) {
1214       for (x = 0; x < 8; ++x, shifter += 2) {
1215         for (j = 0; j < 3; ++j) {
1216           if (block[x] == p[j])
1217             break;
1218         }
1219         flags |= j << shifter;
1220       }
1221       block += 8;
1222
1223       if ((y == 1) || (y == 3)) {
1224         data[0] = flags & 0x000000FF;
1225         data[1] = (flags & 0x0000FF00) >> 8;
1226         data[2] = (flags & 0x00FF0000) >> 16;
1227         data[3] = (flags & 0xFF000000) >> 24;
1228         data += 4;
1229         flags = 0;
1230         shifter = 0;
1231       }
1232     }
1233   }
1234
1235   return apx->error;
1236 }
1237
1238 static guint32
1239 mve_encode_0xab (GstMveEncoderData * enc, const guint8 * src,
1240     GstMveApprox * apx)
1241 {
1242   /* 4-color encoding for left and right half (24 bytes) */
1243   guint8 cols[4];
1244   guint32 flags;
1245   guint i, j, x, y, shifter;
1246   guint8 *block = apx->block;
1247   guint8 *data = apx->data;
1248   const guint8 *p;
1249
1250   apx->error = 0;
1251
1252   for (i = 0; i < 2; ++i) {
1253     apx->error += mve_quantize (enc, src, 4, 8, i, 4, apx->block, cols);
1254
1255     flags = 0;
1256     shifter = 0;
1257
1258     /* p0 > p1 && p4 <= p5 */
1259     data[i] = MAX (cols[0], cols[1]);
1260     data[i ^ 1] = MIN (cols[0], cols[1]);
1261     data[2] = cols[2];
1262     data[3] = cols[3];
1263     p = data;
1264     data += 4;
1265
1266     for (y = 0; y < 8; ++y) {
1267       for (x = 0; x < 4; ++x, shifter += 2) {
1268         for (j = 0; j < 3; ++j) {
1269           if (block[x] == p[j])
1270             break;
1271         }
1272         flags |= j << shifter;
1273       }
1274       block += 8;
1275
1276       if ((y == 3) || (y == 7)) {
1277         data[0] = flags & 0x000000FF;
1278         data[1] = (flags & 0x0000FF00) >> 8;
1279         data[2] = (flags & 0x00FF0000) >> 16;
1280         data[3] = (flags & 0xFF000000) >> 24;
1281         data += 4;
1282         flags = 0;
1283         shifter = 0;
1284       }
1285     }
1286     block = apx->block + 4;
1287   }
1288
1289   return apx->error;
1290 }
1291
1292 static guint32
1293 mve_encode_0xac (GstMveEncoderData * enc, const guint8 * src,
1294     GstMveApprox * apx)
1295 {
1296   /* 4-color encoding for each 4x4 quadrant (32 bytes) */
1297   guint8 cols[4];
1298   guint32 flags;
1299   guint i, j, x, y, shifter;
1300   guint8 *block;
1301   guint8 *data = apx->data;
1302
1303   apx->error = 0;
1304
1305   for (i = 0; i < 4; ++i) {
1306     apx->error +=
1307         mve_quantize (enc, src, 4, 4, ((i & 1) << 1) | ((i & 2) >> 1), 4,
1308         apx->block, cols);
1309
1310     /* p0 <= p1 */
1311     data[0] = MIN (cols[0], cols[1]);
1312     data[1] = MAX (cols[0], cols[1]);
1313     data[2] = cols[2];
1314     data[3] = cols[3];
1315
1316     block = apx->block + ((i / 2) * 4) + ((i % 2) * 32);
1317     flags = 0;
1318     shifter = 0;
1319
1320     for (y = 0; y < 4; ++y) {
1321       for (x = 0; x < 4; ++x, shifter += 2) {
1322         for (j = 0; j < 3; ++j) {
1323           if (block[x] == data[j])
1324             break;
1325         }
1326         flags |= j << shifter;
1327       }
1328       block += 8;
1329     }
1330
1331     data[4] = flags & 0x000000FF;
1332     data[5] = (flags & 0x0000FF00) >> 8;
1333     data[6] = (flags & 0x00FF0000) >> 16;
1334     data[7] = (flags & 0xFF000000) >> 24;
1335     data += 8;
1336   }
1337
1338   return apx->error;
1339 }
1340
1341 static guint32
1342 mve_encode_0xb (GstMveEncoderData * enc, const guint8 * src, GstMveApprox * apx)
1343 {
1344   /* 64-color encoding (each pixel in block is a different color) (64 bytes) */
1345   mve_store_block (enc->mve, src, apx->block);
1346   memcpy (apx->data, apx->block, 64);
1347   apx->error = 0;
1348
1349   return 0;
1350 }
1351
1352 static guint32
1353 mve_encode_0xc (GstMveEncoderData * enc, const guint8 * src, GstMveApprox * apx)
1354 {
1355   /* 16-color block encoding: each 2x2 block is a different color (16 bytes) */
1356   guint i = 0, x, y;
1357   const guint w = enc->mve->width;
1358   guint16 r, g, b;
1359
1360   /* calculate median color for each 2x2 block */
1361   for (y = 0; y < 4; ++y) {
1362     for (x = 0; x < 4; ++x) {
1363       guint32 p = enc->palette[src[0]];
1364
1365       r = MVE_RVAL (p) + 2;
1366       g = MVE_GVAL (p) + 2;
1367       b = MVE_BVAL (p) + 2;
1368
1369       p = enc->palette[src[1]];
1370       r += MVE_RVAL (p);
1371       g += MVE_GVAL (p);
1372       b += MVE_BVAL (p);
1373
1374       p = enc->palette[src[w]];
1375       r += MVE_RVAL (p);
1376       g += MVE_GVAL (p);
1377       b += MVE_BVAL (p);
1378
1379       p = enc->palette[src[w + 1]];
1380       r += MVE_RVAL (p);
1381       g += MVE_GVAL (p);
1382       b += MVE_BVAL (p);
1383
1384       apx->block[i] = apx->block[i + 1] = apx->block[i + 2] =
1385           apx->block[i + 3] = apx->data[i >> 2] =
1386           mve_find_pal_color (enc->palette, MVE_COL (r >> 2, g >> 2, b >> 2));
1387
1388       i += 4;
1389       src += 2;
1390     }
1391     src += (w * 2) - 8;
1392   }
1393
1394   apx->error = mve_block_error_packed (enc, src - (8 * w), apx->block);
1395   return apx->error;
1396 }
1397
1398 static guint32
1399 mve_encode_0xd (GstMveEncoderData * enc, const guint8 * src, GstMveApprox * apx)
1400 {
1401   /* 4-color block encoding: each 4x4 block is a different color (4 bytes) */
1402   guint i, y;
1403
1404   /* calculate median color for each 4x4 block */
1405   for (i = 0; i < 4; ++i) {
1406     guint8 median =
1407         mve_median_sub (enc, src, 4, 4, ((i & 1) << 1) | ((i & 2) >> 1));
1408     guint8 *block = apx->block + ((i / 2) * 4) + ((i % 2) * 32);
1409
1410     for (y = 0; y < 4; ++y) {
1411       memset (block, median, 4);
1412       block += 8;
1413     }
1414
1415     apx->data[i] = median;
1416   }
1417
1418   apx->error = mve_block_error_packed (enc, src, apx->block);
1419   return apx->error;
1420 }
1421
1422 static guint32
1423 mve_encode_0xe (GstMveEncoderData * enc, const guint8 * src, GstMveApprox * apx)
1424 {
1425   /* 1-color encoding: the whole block is 1 solid color (1 bytes) */
1426   guint8 median = mve_median (enc, src);
1427
1428   memset (apx->block, median, 64);
1429
1430   apx->data[0] = median;
1431   apx->error = mve_block_error_packed (enc, src, apx->block);
1432   return apx->error;
1433 }
1434
1435 static guint32
1436 mve_encode_0xf (GstMveEncoderData * enc, const guint8 * src, GstMveApprox * apx)
1437 {
1438   /* 2 colors dithered encoding (2 bytes) */
1439   guint i, x, y;
1440   guint32 r[2] = { 0 }, g[2] = {
1441   0}, b[2] = {
1442   0};
1443   guint8 col[2];
1444
1445   /* find medians for both colors */
1446   for (y = 0; y < 8; ++y) {
1447     for (x = 0; x < 8; x += 2) {
1448       guint16 p = src[x];
1449
1450       r[y & 1] += MVE_RVAL (p);
1451       g[y & 1] += MVE_GVAL (p);
1452       b[y & 1] += MVE_BVAL (p);
1453
1454       p = src[x + 1];
1455       r[(y & 1) ^ 1] += MVE_RVAL (p);
1456       g[(y & 1) ^ 1] += MVE_GVAL (p);
1457       b[(y & 1) ^ 1] += MVE_BVAL (p);
1458     }
1459     src += enc->mve->width;
1460   }
1461   col[0] = mve_find_pal_color (enc->palette,
1462       MVE_COL ((r[0] + 16) / 32, (g[0] + 16) / 32, (b[0] + 16) / 32));
1463   col[1] = mve_find_pal_color (enc->palette,
1464       MVE_COL ((r[1] + 16) / 32, (g[1] + 16) / 32, (b[1] + 16) / 32));
1465
1466   /* store block after encoding */
1467   for (i = 0, y = 0; y < 8; ++y) {
1468     for (x = 0; x < 4; ++x) {
1469       apx->block[i++] = col[y & 1];
1470       apx->block[i++] = col[(y & 1) ^ 1];
1471     }
1472   }
1473
1474   apx->data[0] = col[0];
1475   apx->data[1] = col[1];
1476   apx->error = mve_block_error_packed (enc,
1477       src - (8 * enc->mve->width), apx->block);
1478   return apx->error;
1479 }
1480
1481 /* all available encodings in the preferred order,
1482    i.e. in ascending encoded size */
1483 static const GstMveEncoding mve_encodings[] = {
1484   {0x1, 0, mve_encode_0x1},
1485   {0x0, 0, mve_encode_0x0},
1486   {0xe, 1, mve_encode_0xe},
1487   {0x3, 1, mve_encode_0x3},
1488   {0x4, 1, mve_encode_0x4},
1489   {0x2, 1, mve_encode_0x2},
1490   {0xf, 2, mve_encode_0xf},
1491   {0x5, 2, mve_encode_0x5},
1492   {0xd, 4, mve_encode_0xd},
1493   {0x7, 4, mve_encode_0x7a},
1494   {0x9, 8, mve_encode_0x9a},
1495   {0x7, 10, mve_encode_0x7b},
1496   {0x8, 12, mve_encode_0x8a},
1497   {0x8, 12, mve_encode_0x8b},
1498   {0x9, 12, mve_encode_0x9b},
1499   {0x9, 12, mve_encode_0x9c},
1500   {0xc, 16, mve_encode_0xc},
1501   {0x8, 16, mve_encode_0x8c},
1502   {0x9, 20, mve_encode_0x9d},
1503   {0xa, 24, mve_encode_0xaa},
1504   {0xa, 24, mve_encode_0xab},
1505   {0xa, 32, mve_encode_0xac},
1506   {0xb, 64, mve_encode_0xb}
1507 };
1508
1509 static gboolean
1510 mve_reorder_solution (GArray ** solution, guint16 n)
1511 {
1512   /* do a binary search to find the position to reinsert the modified element */
1513   /* the block we need to reconsider is always at position 0 */
1514   /* return TRUE if this block only has 1 encoding left and can be dropped */
1515   if (mve_comp_solution (&solution[0], &solution[1]) <= 0)
1516     return FALSE;               /* already sorted */
1517
1518   else if (solution[0]->len <= 1)
1519     /* drop this element from further calculations since we cannot improve here */
1520     return TRUE;
1521
1522   else {
1523     /* we know the error value can only get worse, so we can actually start at 1 */
1524     guint lower = 1;
1525     guint upper = n - 1;
1526     gint cmp;
1527     guint idx = 0;
1528
1529     while (upper > lower) {
1530       idx = lower + ((upper - lower) / 2);
1531
1532       cmp = mve_comp_solution (&solution[0], &solution[idx]);
1533
1534       if (cmp < 0) {
1535         upper = idx;
1536       } else if (cmp > 0) {
1537         lower = ++idx;
1538       } else {
1539         upper = lower = idx;
1540       }
1541     }
1542
1543     if (idx > 0) {
1544       /* rearrange array members in new order */
1545       GArray *a = solution[0];
1546
1547       memcpy (&solution[0], &solution[1], sizeof (GArray *) * idx);
1548       solution[idx] = a;
1549     }
1550   }
1551   return FALSE;
1552 }
1553
1554 static guint32
1555 gst_mve_find_solution (GArray ** approx, guint16 n, guint32 size, guint16 max)
1556 {
1557   /* build an array of approximations we can shuffle around */
1558   GstMveApprox *sol_apx;
1559   GArray **solution = g_malloc (sizeof (GArray *) * n);
1560   GArray **current = solution;
1561
1562   memcpy (solution, approx, sizeof (GArray *) * n);
1563
1564   qsort (solution, n, sizeof (GArray *), mve_comp_solution);
1565
1566   do {
1567     /* array is now sorted by error of the next to optimal approximation;
1568        drop optimal approximation for the best block */
1569
1570     /* unable to reduce size further */
1571     if (current[0]->len <= 1)
1572       break;
1573
1574     sol_apx = &g_array_index (current[0], GstMveApprox, current[0]->len - 1);
1575     size -= mve_encodings[sol_apx->type].size;
1576     g_array_remove_index_fast (current[0], current[0]->len - 1);
1577     sol_apx = &g_array_index (current[0], GstMveApprox, current[0]->len - 1);
1578     size += mve_encodings[sol_apx->type].size;
1579
1580     if (mve_reorder_solution (current, n)) {
1581       ++current;
1582       --n;
1583     }
1584   } while (size > max);
1585
1586   g_free (solution);
1587
1588   return size;
1589 }
1590
1591 GstFlowReturn
1592 mve_encode_frame8 (GstMveMux * mve, GstBuffer * frame, const guint32 * palette,
1593     guint16 max_data)
1594 {
1595   guint8 *src;
1596   GstFlowReturn ret = GST_FLOW_ERROR;
1597   guint8 *cm = mve->chunk_code_map;
1598   GArray **approx;
1599   GstMveApprox apx;
1600   GstMveEncoderData enc;
1601   const guint16 blocks = (mve->width * mve->height) / 64;
1602   guint32 encoded_size = 0;
1603   guint i = 0, x, y;
1604
1605   src = GST_BUFFER_DATA (frame);
1606
1607   approx = g_malloc (sizeof (GArray *) * blocks);
1608
1609   enc.mve = mve;
1610   enc.palette = palette;
1611
1612   for (enc.y = 0; enc.y < mve->height; enc.y += 8) {
1613     for (enc.x = 0; enc.x < mve->width; enc.x += 8) {
1614       guint32 err, last_err = MVE_APPROX_MAX_ERROR;
1615       guint type = 0;
1616       guint best = 0;
1617
1618       enc.q2available = enc.q4available = FALSE;
1619       approx[i] = g_array_new (FALSE, FALSE, sizeof (GstMveApprox));
1620
1621       do {
1622         err = mve_encodings[type].approx (&enc, src, &apx);
1623
1624         if (err < last_err) {
1625           apx.type = best = type;
1626           g_array_append_val (approx[i], apx);
1627           last_err = err;
1628         }
1629
1630         ++type;
1631       } while (last_err != 0);
1632
1633       encoded_size += mve_encodings[best].size;
1634       ++i;
1635       src += 8;
1636     }
1637     src += 7 * mve->width;
1638   }
1639
1640   /* find best solution with size constraints */
1641   GST_DEBUG_OBJECT (mve, "encoded frame %u in %u bytes (lossless)",
1642       mve->video_frames + 1, encoded_size);
1643
1644 #if 0
1645   /* FIXME */
1646   src = GST_BUFFER_DATA (frame);
1647   for (i = 0, y = 0; y < mve->height; y += 8) {
1648     for (x = 0; x < mve->width; x += 8, ++i) {
1649       GstMveApprox *sol =
1650           &g_array_index (approx[i], GstMveApprox, approx[i]->len - 1);
1651       guint opcode = mve_encodings[sol->type].opcode;
1652       guint j, k;
1653
1654       if (sol->error > 0)
1655         GST_WARNING_OBJECT (mve, "error is %lu for %d/%d (0x%x)", sol->error, x,
1656             y, opcode);
1657
1658       for (j = 0; j < 8; ++j) {
1659         guint8 *o = src + j * mve->width;
1660         guint8 *c = sol->block + j * 8;
1661
1662         if (memcmp (o, c, 8)) {
1663           GST_WARNING_OBJECT (mve, "opcode 0x%x (type %d) at %d/%d, line %d:",
1664               opcode, sol->type, x, y, j + 1);
1665           for (k = 0; k < 8; ++k) {
1666             o = src + k * mve->width;
1667             c = sol->block + k * 8;
1668             GST_WARNING_OBJECT (mve,
1669                 "%d should be: %4d  %4d  %4d  %4d  %4d  %4d  %4d  %4d", k, o[0],
1670                 o[1], o[2], o[3], o[4], o[5], o[6], o[7]);
1671             GST_WARNING_OBJECT (mve,
1672                 "%d but is   : %4d  %4d  %4d  %4d  %4d  %4d  %4d  %4d", k, c[0],
1673                 c[1], c[2], c[3], c[4], c[5], c[6], c[7]);
1674           }
1675         }
1676       }
1677       src += 8;
1678     }
1679     src += 7 * mve->width;
1680   }
1681 #endif
1682
1683   if (encoded_size > max_data) {
1684     encoded_size =
1685         gst_mve_find_solution (approx, blocks, encoded_size, max_data);
1686     if (encoded_size > max_data) {
1687       GST_ERROR_OBJECT (mve, "unable to compress frame to less than %d bytes",
1688           encoded_size);
1689       for (i = 0; i < blocks; ++i)
1690         g_array_free (approx[i], TRUE);
1691
1692       goto done;
1693     }
1694     GST_DEBUG_OBJECT (mve, "compressed frame %u to %u bytes (lossy)",
1695         mve->video_frames + 1, encoded_size);
1696   }
1697
1698   mve->chunk_video = g_byte_array_sized_new (encoded_size);
1699
1700   /* encode */
1701   src = GST_BUFFER_DATA (frame);
1702   for (i = 0, y = 0; y < mve->height; y += 8) {
1703     for (x = 0; x < mve->width; x += 8, ++i) {
1704       GstMveApprox *sol =
1705           &g_array_index (approx[i], GstMveApprox, approx[i]->len - 1);
1706       guint opcode = mve_encodings[sol->type].opcode;
1707
1708       g_byte_array_append (mve->chunk_video, sol->data,
1709           mve_encodings[sol->type].size);
1710
1711       if (i & 1) {
1712         *cm |= opcode << 4;
1713         ++cm;
1714       } else
1715         *cm = opcode;
1716
1717       /* modify the frame to match the image we actually encoded */
1718       if (sol->error > 0)
1719         mve_restore_block (mve, src, sol->block);
1720
1721       src += 8;
1722       g_array_free (approx[i], TRUE);
1723     }
1724     src += 7 * mve->width;
1725   }
1726
1727   ret = GST_FLOW_OK;
1728
1729 done:
1730   g_free (approx);
1731
1732   return ret;
1733 }