[FFmpeg-devel] [PATCH] X-Face image encoder and decoder
Stefano Sabatini
stefasab at gmail.com
Sun Oct 14 00:39:27 CEST 2012
On date Saturday 2012-10-13 19:20:40 +0000, Paul B Mahol encoded:
> On 10/13/12, Stefano Sabatini <stefasab at gmail.com> wrote:
> > On date Saturday 2012-10-13 19:50:27 +0200, Stefano Sabatini encoded:
> >> On date Saturday 2012-10-13 01:44:43 +0200, Stefano Sabatini encoded:
> >> [...]
> >> > Patch updated.
> >> >
> >> > Note: what's the best way to check encoder+decoder in FATE? Also
> >> > what's the recommended way to add an xface test? Would this require to
> >> > add a sample to SAMPLES, or should we rely on the encoder?.
> >>
> >> Updated patch.
> >>
> >> I'm also attaching the patch for adding a FATE test, together with
> >> sample to upload.
> >
> > Updated with a few fixes spotted by durandal on IRC.
> >
> > I'll push both patches in a few days if I read no more comments.
>
>
> [...]
> > diff --git a/libavcodec/xface.c b/libavcodec/xface.c
> > new file mode 100644
> > index 0000000..08f09fd
> > --- /dev/null
> > +++ b/libavcodec/xface.c
> > @@ -0,0 +1,385 @@
> > +/*
> > + * Copyright (c) 1990 James Ashton - Sydney University
> > + * Copyright (c) 2012 Stefano Sabatini
> > + *
> > + * This file is part of FFmpeg.
> > + *
> > + * FFmpeg is free software; you can redistribute it and/or
> > + * modify it under the terms of the GNU Lesser General Public
> > + * License as published by the Free Software Foundation; either
> > + * version 2.1 of the License, or (at your option) any later version.
> > + *
> > + * FFmpeg is distributed in the hope that it will be useful,
> > + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> > + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> > + * Lesser General Public License for more details.
> > + *
> > + * You should have received a copy of the GNU Lesser General Public
> > + * License along with FFmpeg; if not, write to the Free Software
> > + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> > + */
> > +
> > +/**
> > + * @file
> > + * X-Face common data and utilities definition.
> > + */
> > +
> > +#include <stdint.h>
>
> not needed
removed
> > +#include "xface.h"
> > +
> > +void ff_big_add(BigInt *b, uint8_t a)
> > +{
> > + int i;
> > + uint8_t *w;
> > + uint16_t c;
> > +
> > + a &= XFACE_WORDMASK;
> > + if (a == 0)
> > + return;
> > + i = 0;
> > + w = b->words;
> > + c = a;
> > + while (i < b->nb_words && c) {
> > + c += (uint16_t)*w;
> > + *w++ = (uint8_t)(c & XFACE_WORDMASK);
> > + c >>= XFACE_BITSPERWORD;
> > + i++;
> > + }
> > + if (i == b->nb_words && c) {
> > + b->nb_words++;
> > + *w = (uint16_t)(c & XFACE_WORDMASK);
> > + }
> > +}
> > +
> > +void ff_big_div(BigInt *b, uint8_t a, uint8_t *r)
> > +{
> > + int i;
> > + uint8_t *w;
> > + uint16_t c, d;
> > +
> > + a &= XFACE_WORDMASK;
> > + if (a == 1 || b->nb_words == 0) {
> > + *r = 0;
> > + return;
> > + }
> > +
> > + /* treat this as a == WORDCARRY and just shift everything right a WORD */
> > + if (a == 0) {
> > + i = --b->nb_words;
> > + w = b->words;
> > + *r = *w;
> > + while (i--) {
> > + *w = *(w + 1);
> > + w++;
> > + }
> > + *w = 0;
> > + return;
> > + }
> > + w = b->words + (i = b->nb_words);
> > + c = 0;
> > + while (i--) {
> > + c <<= XFACE_BITSPERWORD;
> > + c += (uint16_t)*--w;
> > + d = c / (uint16_t)a;
> > + c = c % (uint16_t)a;
> > + *w = (uint8_t)(d & XFACE_WORDMASK);
> > + }
> > + *r = c;
> > + if (b->words[b->nb_words - 1] == 0)
> > + b->nb_words--;
> > +}
> > +
> > +void ff_big_mul(BigInt *b, uint8_t a)
> > +{
> > + int i;
> > + uint8_t *w;
> > + uint16_t c;
> > +
> > + a &= XFACE_WORDMASK;
> > + if (a == 1 || b->nb_words == 0)
> > + return;
> > + if (a == 0) {
> > + /* treat this as a == WORDCARRY and just shift everything left a WORD */
> > + i = b->nb_words++;
> > + w = b->words + i;
> > + while (i--) {
> > + *w = *(w - 1);
> > + w--;
> > + }
> > + *w = 0;
> > + return;
> > + }
> > + i = b->nb_words;
> > + w = b->words;
> > + c = 0;
> > + while (i--) {
> > + c += (uint16_t)*w * (uint16_t)a;
> > + *(w++) = (uint8_t)(c & XFACE_WORDMASK);
> > + c >>= XFACE_BITSPERWORD;
> > + }
> > + if (c) {
> > + b->nb_words++;
> > + *w = (uint16_t)(c & XFACE_WORDMASK);
> > + }
> > +}
> > +
> > +ProbRange ff_xface_probranges_per_level[4][3] = {
> > + // black grey white
> > + { { 1, 255}, {251, 0}, { 4, 251} }, /* Top of tree almost always grey */
> > + { { 1, 255}, {200, 0}, { 55, 200} },
> > + { { 33, 223}, {159, 0}, { 64, 159} },
> > + { {131, 0}, { 0, 0}, {125, 131} }, /* Grey disallowed at bottom */
> > +};
>
> const?
yes
> > +
> > +ProbRange ff_xface_probranges_2x2[16] = {
> > + { 0, 0}, {38, 0}, {38, 38}, {13, 152},
> > + {38, 76}, {13, 165}, {13, 178}, { 6, 230},
> > + {38, 114}, {13, 191}, {13, 204}, { 6, 236},
> > + {13, 217}, { 6, 242}, { 5, 248}, { 3, 253},
> > +};
>
> const?
yes
> > +
> > +/*
> > + * The "guess the next pixel" tables follow. Normally there are 12
> > + * neighbour pixels used to give 1<<12 cases as we get closer to the
> > + * upper left corner lesser numbers of neighbours are available.
> > + *
> > + * Each byte in the tables represents 8 boolean values starting from
> > + * the most significant bit, so for accessing the bitmap value at
> > + * position k, it is necessary to do:
> > + * !!(table[k>>3] & 0x80>>(k&7))
> > + */
> > +
> > +static const uint8_t g_00[1<<9] = {
> > + 0x00, 0x00, 0x01, 0x01, 0x00, 0x00, 0xe3, 0xdf, 0x05, 0x17,
> > + 0x05, 0x0f, 0x00, 0x1b, 0x0f, 0xdf, 0x00, 0x04, 0x00, 0x00,
> > + 0x0d, 0x0f, 0x03, 0x7f, 0x00, 0x00, 0x00, 0x01, 0x00, 0x1d,
> > + 0x45, 0x2f, 0x00, 0x00, 0x00, 0x0d, 0x00, 0x0a, 0xff, 0xff,
> > + 0x00, 0x04, 0x00, 0x05, 0x01, 0x3f, 0xcf, 0xff, 0x10, 0x01,
> > + 0x80, 0xc9, 0x0f, 0x0f, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
> > + 0x1b, 0x1f, 0xff, 0xff, 0x4f, 0x54, 0x07, 0x1f, 0x57, 0x47,
> > + 0xd7, 0x3d, 0xff, 0xff, 0x5f, 0x1f, 0x7f, 0xff, 0x7f, 0x7f,
> > + 0x05, 0x0f, 0x01, 0x0f, 0x0f, 0x5f, 0x9b, 0xdf, 0x7f, 0xff,
> > + 0x5f, 0x1d, 0x5f, 0xff, 0x0f, 0x1f, 0x0f, 0x5f, 0x03, 0x1f,
> > + 0x4f, 0x5f, 0xf7, 0x7f, 0x7f, 0xff, 0x0d, 0x0f, 0xfb, 0xff,
> > + 0xf7, 0xbf, 0x0f, 0x4f, 0xd7, 0x3f, 0x4f, 0x7f, 0xff, 0xff,
> > + 0x67, 0xbf, 0x56, 0x25, 0x1f, 0x7f, 0x9f, 0xff, 0x00, 0x00,
> > + 0x00, 0x05, 0x5f, 0x7f, 0x01, 0xdf, 0x14, 0x00, 0x05, 0x0f,
> > + 0x07, 0xa2, 0x09, 0x0f, 0x00, 0x00, 0x00, 0x00, 0x0f, 0x5f,
> > + 0x18, 0xd7, 0x94, 0x71, 0x00, 0x05, 0x1f, 0xb7, 0x0c, 0x07,
> > + 0x0f, 0x0f, 0x00, 0x0f, 0x0f, 0x1f, 0x84, 0x8f, 0x05, 0x15,
> > + 0x05, 0x0f, 0x4f, 0xff, 0x87, 0xdf, 0x05, 0x01, 0x10, 0x00,
> > + 0x0f, 0x0f, 0x00, 0x08, 0x05, 0x04, 0x04, 0x01, 0x4f, 0xff,
> > + 0x9f, 0x8f, 0x4a, 0x40, 0x5f, 0x5f, 0xff, 0xfe, 0xdf, 0xff,
> > + 0x7f, 0xf7, 0xff, 0x7f, 0xff, 0xff, 0x7b, 0xff, 0x0f, 0xfd,
> > + 0xd7, 0x5f, 0x4f, 0x7f, 0x7f, 0xdf, 0xff, 0xff, 0xff, 0xff,
> > + 0xff, 0x77, 0xdf, 0x7f, 0x4f, 0xef, 0xff, 0xff, 0x77, 0xff,
> > + 0xff, 0xff, 0x6f, 0xff, 0x0f, 0x4f, 0xff, 0xff, 0x9d, 0xff,
> > + 0x0f, 0xef, 0xff, 0xdf, 0x6f, 0xff, 0xff, 0xff, 0x4f, 0xff,
> > + 0xcd, 0x0f, 0x4f, 0xff, 0xff, 0xdf, 0x00, 0x00, 0x00, 0x0b,
> > + 0x05, 0x02, 0x02, 0x0f, 0x04, 0x00, 0x00, 0x0c, 0x01, 0x06,
> > + 0x00, 0x0f, 0x20, 0x03, 0x00, 0x00, 0x05, 0x0f, 0x40, 0x08,
> > + 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x0c, 0x0f, 0x01, 0x00,
> > + 0x80, 0x00, 0x00, 0x00, 0x80, 0x00, 0x00, 0x14, 0x01, 0x05,
> > + 0x01, 0x15, 0xaf, 0x0f, 0x00, 0x01, 0x10, 0x00, 0x08, 0x00,
> > + 0x46, 0x0c, 0x20, 0x00, 0x88, 0x00, 0x0f, 0x15, 0xff, 0xdf,
> > + 0x02, 0x00, 0x00, 0x0f, 0x7f, 0x5f, 0xdb, 0xff, 0x4f, 0x3e,
> > + 0x05, 0x0f, 0x7f, 0xf7, 0x95, 0x4f, 0x0d, 0x0f, 0x01, 0x0f,
> > + 0x4f, 0x5f, 0x9f, 0xdf, 0x25, 0x0e, 0x0d, 0x0d, 0x4f, 0x7f,
> > + 0x8f, 0x0f, 0x0f, 0xfa, 0x04, 0x4f, 0x4f, 0xff, 0xf7, 0x77,
> > + 0x47, 0xed, 0x05, 0x0f, 0xff, 0xff, 0xdf, 0xff, 0x4f, 0x6f,
> > + 0xd8, 0x5f, 0x0f, 0x7f, 0xdf, 0x5f, 0x07, 0x0f, 0x94, 0x0d,
> > + 0x1f, 0xff, 0xff, 0xff, 0x00, 0x02, 0x00, 0x03, 0x46, 0x57,
> > + 0x01, 0x0d, 0x01, 0x08, 0x01, 0x0f, 0x47, 0x6c, 0x0d, 0x0f,
> > + 0x02, 0x00, 0x00, 0x00, 0x0b, 0x4f, 0x00, 0x08, 0x05, 0x00,
> > + 0x95, 0x01, 0x0f, 0x7f, 0x0c, 0x0f, 0x01, 0x0e, 0x00, 0x00,
> > + 0x0f, 0x41, 0x00, 0x00, 0x04, 0x24, 0x0d, 0x0f, 0x0f, 0x7f,
> > + 0xcf, 0xdf, 0x00, 0x00, 0x00, 0x00, 0x04, 0x40, 0x00, 0x00,
> > + 0x06, 0x26, 0xcf, 0x05, 0xcf, 0x7f, 0xdf, 0xdf, 0x00, 0x00,
> > + 0x17, 0x5f, 0xff, 0xfd, 0xff, 0xff, 0x46, 0x09, 0x4f, 0x5f,
> > + 0x7f, 0xfd, 0xdf, 0xff, 0x0a, 0x88, 0xa7, 0x7f, 0x7f, 0xff,
> > + 0xff, 0xff, 0x0f, 0x04, 0xdf, 0x7f, 0x4f, 0xff, 0x9f, 0xff,
> > + 0x0e, 0xe6, 0xdf, 0xff, 0x7f, 0xff, 0xff, 0xff, 0x0f, 0xec,
> > + 0x8f, 0x4f, 0x7f, 0xff, 0xdf, 0xff, 0x0f, 0xcf, 0xdf, 0xff,
> > + 0x6f, 0x7f, 0xff, 0xff, 0x03, 0x0c, 0x9d, 0x0f, 0x7f, 0xff,
> > + 0xff, 0xff,
> > +};
> > +
> > +static const uint8_t g_01[1<<4] = {
> > + 0x37, 0x73, 0x00, 0x19, 0x57, 0x7f, 0xf5, 0xfb, 0x70, 0x33,
> > + 0xf0, 0xf9, 0x7f, 0xff, 0xff, 0xff,
> > +};
> > +
> > +static const uint8_t g_02[1<<0] = {
> > + 0x50,
> > +};
> > +
> > +static const uint8_t g_10[1<<6] = {
> > + 0x00, 0x00, 0x00, 0x00, 0x50, 0x00, 0xf3, 0x5f, 0x84, 0x04,
> > + 0x17, 0x9f, 0x04, 0x23, 0x05, 0xff, 0x00, 0x00, 0x00, 0x02,
> > + 0x03, 0x03, 0x33, 0xd7, 0x05, 0x03, 0x5f, 0x3f, 0x17, 0x33,
> > + 0xff, 0xff, 0x00, 0x80, 0x02, 0x04, 0x12, 0x00, 0x11, 0x57,
> > + 0x05, 0x25, 0x05, 0x03, 0x35, 0xbf, 0x9f, 0xff, 0x07, 0x6f,
> > + 0x20, 0x40, 0x17, 0x06, 0xfa, 0xe8, 0x01, 0x07, 0x1f, 0x9f,
> > + 0x1f, 0xff, 0xff, 0xff,
> > +};
> > +
> > +static const uint8_t g_20[1<<3] = {
> > + 0x04, 0x00, 0x01, 0x01, 0x43, 0x2e, 0xff, 0x3f,
> > +};
> > +
> > +static const uint8_t g_30[1<<5] = {
> > + 0x11, 0x11, 0x11, 0x11, 0x51, 0x11, 0x13, 0x11, 0x11, 0x11,
> > + 0x13, 0x11, 0x11, 0x11, 0x33, 0x11, 0x13, 0x11, 0x13, 0x13,
> > + 0x13, 0x13, 0x31, 0x31, 0x11, 0x01, 0x11, 0x11, 0x71, 0x11,
> > + 0x11, 0x75,
> > +};
> > +
> > +static const uint8_t g_40[1<<7] = {
> > + 0x00, 0x0f, 0x00, 0x09, 0x00, 0x0d, 0x00, 0x0d, 0x00, 0x0f,
> > + 0x00, 0x4e, 0xe4, 0x0d, 0x10, 0x0f, 0x00, 0x0f, 0x44, 0x4f,
> > + 0x00, 0x1e, 0x0f, 0x0f, 0xae, 0xaf, 0x45, 0x7f, 0xef, 0xff,
> > + 0x0f, 0xff, 0x00, 0x09, 0x01, 0x11, 0x00, 0x01, 0x1c, 0xdd,
> > + 0x00, 0x15, 0x00, 0xff, 0x00, 0x10, 0x00, 0xfd, 0x00, 0x0f,
> > + 0x4f, 0x5f, 0x3d, 0xff, 0xff, 0xff, 0x4f, 0xff, 0x1c, 0xff,
> > + 0xdf, 0xff, 0x8f, 0xff, 0x00, 0x0d, 0x00, 0x00, 0x00, 0x15,
> > + 0x01, 0x07, 0x00, 0x01, 0x02, 0x1f, 0x01, 0x11, 0x05, 0x7f,
> > + 0x00, 0x1f, 0x41, 0x57, 0x1f, 0xff, 0x05, 0x77, 0x0d, 0x5f,
> > + 0x4d, 0xff, 0x4f, 0xff, 0x0f, 0xff, 0x00, 0x00, 0x02, 0x05,
> > + 0x00, 0x11, 0x05, 0x7d, 0x10, 0x15, 0x2f, 0xff, 0x40, 0x50,
> > + 0x0d, 0xfd, 0x04, 0x0f, 0x07, 0x1f, 0x07, 0x7f, 0x0f, 0xbf,
> > + 0x0d, 0x7f, 0x0f, 0xff, 0x4d, 0x7d, 0x0f, 0xff,
> > +};
> > +
> > +static const uint8_t g_11[1<<2] = {
> > + 0x01, 0x13, 0x03, 0x7f,
> > +};
>
> Above, and bellow I really do not see point in 1<<X dance.
> Do tables need padding?
Well I find 1<<9 slightly more readable than 512, but sure I can
replace them with decimals.
>
> > +
> > +static const uint8_t g_21[1<<0] = {
> > + 0x17,
> > +};
> > +
> > +static const uint8_t g_31[1<<2] = {
> > + 0x55, 0x57, 0x57, 0x7f,
> > +};
> > +
> > +static const uint8_t g_41[1<<3] = {
> > + 0x01, 0x01, 0x01, 0x1f, 0x03, 0x1f, 0x3f, 0xff,
> > +};
> > +
> > +static const uint8_t g_12[1<<0] = {
> > + 0x40,
> > +};
> > +
> > +static const uint8_t g_22[1<<0] = {
> > + 0x00,
> > +};
> > +
> > +static const uint8_t g_32[1<<0] = {
> > + 0x10,
> > +};
> > +
> > +static const uint8_t g_42[1<<0] = {
> > + 0x10,
> > +};
> > +
> [...]
>
> > diff --git a/libavcodec/xface.h b/libavcodec/xface.h
> > new file mode 100644
> > index 0000000..d7ffd3f
> > --- /dev/null
> > +++ b/libavcodec/xface.h
> > @@ -0,0 +1,95 @@
> [...]
>
> > +#define XFACE_WORDCARRY (1 << XFACE_BITSPERWORD)
> > +#define XFACE_WORDMASK (XFACE_WORDCARRY - 1)
> > +
> > +#define XFACE_MAX_WORDS ((XFACE_PIXELS * 2 + XFACE_BITSPERWORD - 1) / XFACE_BITSPERWORD)
> > +
> > +/* Portable, very large unsigned integer arithmetic is needed.
> > + * Implementation uses arrays of WORDs. */
> > +typedef struct {
> > + int nb_words;
> > + uint8_t words[XFACE_MAX_WORDS];
> > +} BigInt;
>
> anonymous typedef (trend is to give them name)
typedef struct BigInt {...} BigInt;
seems a bit redundant, since I never use struct BigInt. I'll skip this
comment unless there is a technical reason for that or if people
insist.
> > +
> > +/**
> > + * Add a to b storing the result in b.
> > + */
> > +void ff_big_add(BigInt *b, uint8_t a);
> > +
> > +/**
> > + * Divide b by a storing the result in b and the remainder in the word
> > + * pointed to by r.
> > + */
> > +void ff_big_div(BigInt *b, uint8_t a, uint8_t *r);
> > +
> > +/**
> > + * Multiply a by b storing the result in b.
> > + */
> > +void ff_big_mul(BigInt *b, uint8_t a);
> > +
> > +/* Each face is encoded using 9 octrees of 16x16 each. Each level of the
> > + * trees has varying probabilities of being white, grey or black.
> > + * The table below is based on sampling many faces */
> > +enum { BLACK = 0, GREY, WHITE };
>
> give it name?
XFaceColor (yes it is a bit semantically inconsistent, hopefully
nobody will notice).
> > +
> > +/* Data of varying probabilities are encoded by a value in the range 0 - 255.
> > + * The probability of the data determines the range of possible encodings.
> > + * Offset gives the first possible encoding of the range. */
> > +typedef struct {
> > + int range;
> > + int offset;
> > +} ProbRange;
>
> anonymous typedef here and in other places ...
As above.
I'll post an updated patch later (after addressing other comments).
--
FFmpeg = Frenzy Fast Mysterious Peaceful Ecstatic Geisha
More information about the ffmpeg-devel
mailing list