On Fri, Aug 06, 2010 at 06:26:38PM +0400, Alexey Tourbin wrote:
> 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", которое в данном случае
обозначает 1111(01|10|11), можно использовать старшие 11, не
заглядывая далее.

> Потому что следующая буква тоже может быть "Z" и т.д.  Тогда надо класть
> Z в стек и распаковывать в обратном порядке.  Это слишком сложно.
> Распаковка должна работать быстро и быть более-менее тривиальной.
> Тогда можно попытаться сделать так, чтобы после первого Z никогда
> не могло идти второе Z.
> 
>     char bitv[] = {
> 	1, 0, 1, 1, 1, 1,
> 	1, 1, 1, 1, 1, 0,
>     };