[devel] base2 <-> base62

[Alexey Tourbin]

On Fri, Aug 06, 2010 at 05:17:19PM +0400, Alexey Tourbin wrote:
> Но с первого раза у меня опять не получилось написать декодирование.
> Кто хочет мне помочь?  Вот полностью кодирование.  После декодирования
> разрешается, чтобы массив bitv[] содержал в конце несколько лишних
> нулей.
> 
>     const char *bitv_to_base62(int bitc, char bitv[])
>     {
> 	int base62c = 0;
> 	char *base62v = NULL;
> 	void put_char(int c)
> 	{
> 	    int realloc_delta = 1024;
> 	    if ((base62c & (realloc_delta - 1)) == 0)
> 		base62v = realloc(base62v, sizeof(*base62v) * (base62c + realloc_delta));
> 	    base62v[base62c++] = c;
> 	}
> 	void put_digit(int c)
> 	{
> 	    if (c < 10)
> 		put_char(c + '0');
> 	    else if (c < 36)
> 		put_char(c - 10 + 'a');
> 	    else if (c < 62)
> 		put_char(c - 36 + 'A');
> 	}
> 	int i;
> 	int bits6 = 0;
> 	int num6b = 0;
> 	for (i = 0; i < bitc; i++) {
> 	    if (bits6 < 6)
> 		num6b |= bitv[i] << bits6++;
> 	    if (bits6 == 6) {
> 		switch (num6b) {
> 		case 61:
> 		    put_digit(61);
> 		    // extra "0" binary bit
> 		    bits6 = 1;
> 		    num6b = 0;
> 		    break;
> 		case 62:
> 		    put_digit(61);
> 		    // extra "10" binary bits
> 		    bits6 = 2;
> 		    num6b = 1;
> 		    break;
> 		case 63:
> 		    put_digit(61);
> 		    // extra "11" binary bits
> 		    bits6 = 2;
> 		    num6b = 3;
> 		    break;
> 		default:
> 		    assert(num6b < 61);
> 		    put_digit(num6b);
> 		    bits6 = 0;
> 		    num6b = 0;
> 		    break;
> 		}
> 	    }
> 	}
> 	if (bits6) {
> 	    assert(num6b < 61);
> 	    put_digit(num6b);
> 	}
> 	put_char(0);
> 	return base62v;
>     }

Нужно учитывать, что значение 61 (Z) может идти два или более раза
подряд.  Например, следующий bitv[] кодируется в "ZZ1".  Это значит,
что мы не можем сразу же распаковать "Z", посмотрев на следующую букву.
Потому что следующая буква тоже может быть "Z" и т.д.  Тогда надо класть
Z в стек и распаковывать в обратном порядке.  Это слишком сложно.
Распаковка должна работать быстро и быть более-менее тривиальной.
Тогда можно попытаться сделать так, чтобы после первого Z никогда
не могло идти второе Z.

    char bitv[] = {
	1, 0, 1, 1, 1, 1,
	1, 1, 1, 1, 1, 0,
    };
----------- следующая часть -----------
Было удалено вложение не в текстовом формате...
Имя     : отсутствует
Тип     : application/pgp-signature
Размер  : 198 байтов
Описание: отсутствует
Url     : <http://lists.altlinux.org/pipermail/devel/attachments/20100806/03353ee4/attachment.bin>