[FFmpeg-devel] [PATCH] X-Face image encoder and decoder

Paul B Mahol onemda at gmail.com
Sat Oct 13 21:20:40 CEST 2012


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

> +#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?
> +
> +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?
> +
> +/*
> + * 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?

> +
> +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)
> +
> +/**
> + * 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?
> +
> +/* 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 ...
> +
> +extern ProbRange ff_xface_probranges_per_level[4][3];
> +
> +extern ProbRange ff_xface_probranges_2x2[16];
> +
> +void ff_xface_generate_face(uint8_t *dst, uint8_t * const src);

[...]


More information about the ffmpeg-devel mailing list