64-bit GUID's хеш в XML документе

Все, что вы хотели знать о программизме, но боялись спросить.
vg
Маньяк
Сообщения: 2803
Зарегистрирован: 29 май 2003, 22:29
Откуда: Магадан - Миссиссага

64-bit GUID's хеш в XML документе

Сообщение vg »

Необходимо создать строковое представление "уникального" UID длиной 16 _символов_.

ПО нашего партнёра требует, чтобы каждый наш XML документ, направляемый этому партнёру, содержал уникальный UID длиной 16 символов. При этом он предъявляет странноватое требование, что мол, это должен быть GUID (128 бит).
Однако, непосредственно строковое представление GUID в XML документе, типа DocID = "da2ea19c3b394356a54eb6656b60a23b", программа нашего партнёра не воспринимает, т.к. максимальная длина этого поля в их ПО равна 16 символам. "Уникальность" должна быть обеспечена с большой вероятностью, хотя одна коллизия допускается и может быть разрешена (я буду проверять по нашей базе UID для всех документов).

Вопрос как получить UID-дообразный 16 символьный хеш, например GUID, который можно было без проверок на допустимые символы использовать в XML (желательно без сложных алгоритмов проверки и замены недопустимых символов).

Предлагается тупо:

1) получить GUID a массив BYTE b[16].

2) применить XOR:
b[0] = b[0]^b[8];
b[1] = b[1]^b[9];
...
b[7] = b[7]^b[15];

3) первые 16 байт, b[0]-b[15] писать в XML в base16. Это и будет UID.

4) проверить коллизии, и если есть, то повторить один раз, предполагая, что вероятность второй коллизии ничтожно мала.

С# код мог быть таков:

Код: Выделить всё

            System.Guid guid = System.Guid.NewGuid();

            // guid = {da2ea19c-3b39-4356-a54e-b6656b60a23b}
            // string s = guid.ToString();
            // s = "da2ea19c3b394356" + "a54eb6656b60a23b"

            byte[] b = guid.ToByteArray();
            //[0]	156
            //[1]	161
            //[2]	46
            //[3]	218
            //[4]	57
            //[5]	59
            //[6]	86
            //[7]	67

            //[8]	165
            //[9]	78
            //[10]  182
            //[11]  101
            //[12]  107
            //[13]  96
            //[14]  162
            //[15]  59

            int offset = b.Length / 2;
            for (int i = 0; i < offset; i++)
            {
                b[i] ^= b[offset + i];
            }

            //[0] 57
            //[1]	239
            //[2]	152
            //[3]	191
            //[4]	82
            //[5]	91
            //[6]	244
            //[7]	120

            //[8]	165
            //[9]	78
            //[10]  182
            //[11]  101
            //[12]  107
            //[13]  96
            //[14]  162
            //[15]  59

            string sxor = "";
            for(int i = 0; i < b.Length; i++)
            {
                sxor += Convert.ToString(b[i], 16);
            }

            //sxor = "39ef98bf525bf478" + "a54eb6656b60a23b"

            sxor = sxor.Substring( 0, offset) ;

            //sxor = "39ef98bf525bf478" ;

Аватара пользователя
sobomax
Маньяк
Сообщения: 3699
Зарегистрирован: 29 июн 2006, 22:53
Откуда: Vancouver

Сообщение sobomax »

Не изобретайте велосипед - используйте стандартные алгоритмы хеширования типа MD5. Там правда длина хеша - 16 байт то есть 32 hex символа, но можно спокойно взять только первых 16.

-Maxim
Аватара пользователя
Marmot
Графоман
Сообщения: 39279
Зарегистрирован: 17 фев 2003, 17:58
Откуда: Caulfeild
Контактная информация:

Сообщение Marmot »

sobomax писал(а):Не изобретайте велосипед - используйте стандартные алгоритмы хеширования типа MD5. Там правда длина хеша - 16 байт то есть 32 hex символа, но можно спокойно взять только первых 16.
А если сделать custom base64 0-9,a-Z,A-Z,_. то можно и ещё больше битиков в 16 символов напихать.

PS
Кстати, вот подумал, а если просто использовать timestamp в миллисекундах.
Это как раз 8 байтов, не думаю что вы генерите документы с частотой большей, чем разрешение системного таймера.
Даже если документы генерятся на нескольких машинах вероятность коллизии достаточно мала.
Аватара пользователя
aissp
Маньяк
Сообщения: 2710
Зарегистрирован: 07 ноя 2005, 09:51

Сообщение aissp »

Угу

http://www.antichat.ru/txt/hashes/

типа вот так и выбирай на вкус.
Аватара пользователя
sobomax
Маньяк
Сообщения: 3699
Зарегистрирован: 29 июн 2006, 22:53
Откуда: Vancouver

Сообщение sobomax »

Marmot писал(а):
sobomax писал(а):Не изобретайте велосипед - используйте стандартные алгоритмы хеширования типа MD5. Там правда длина хеша - 16 байт то есть 32 hex символа, но можно спокойно взять только первых 16.
А если сделать custom base64 0-9,a-Z,A-Z,_. то можно и ещё больше битиков в 16 символов напихать.
Смысла нет никакого. Даже с 64-мя битами от полных 128 и использованием нормального алгоритма (типа MD5) вероятность коллизии настолько мала что ею вполне возможно просто пренебречь и не морочить себе голову с изобретением того как пихать биты. Использовать стандартные процедуры получения hex представления которые есть в любой библиотеке которая реализует MD5.

-Maxim
Аватара пользователя
Ranger
Маньяк
Сообщения: 1199
Зарегистрирован: 22 окт 2003, 18:28
Откуда: 2:5025 -> Burnaby

Сообщение Ranger »

Marmot писал(а):просто использовать timestamp в миллисекундах
еще проще использовать обычную последовательность next = prev + 1 ;)
Аватара пользователя
dima
Житель
Сообщения: 690
Зарегистрирован: 19 фев 2003, 19:26
Откуда: Хабаровск->Toronto

Сообщение dima »

Сгенерируй GUID, перевери его в строку и посчитай MD5 этой строки.
Аватара пользователя
Marmot
Графоман
Сообщения: 39279
Зарегистрирован: 17 фев 2003, 17:58
Откуда: Caulfeild
Контактная информация:

Сообщение Marmot »

Ranger писал(а):
Marmot писал(а):просто использовать timestamp в миллисекундах
еще проще использовать обычную последовательность next = prev + 1 ;)
Неа, не проще, если есть несколько серверов тогда это значение надо как-то шарить, и т.д.
Часы удобнее.
Аватара пользователя
Marmot
Графоман
Сообщения: 39279
Зарегистрирован: 17 фев 2003, 17:58
Откуда: Caulfeild
Контактная информация:

Сообщение Marmot »

dima писал(а):Сгенерируй GUID, перевери его в строку и посчитай MD5 этой строки.
Эх, сейчас вот придёт Зотин и научит нас всех процессорные циклы экономить :evil:
vg
Маньяк
Сообщения: 2803
Зарегистрирован: 29 май 2003, 22:29
Откуда: Магадан - Миссиссага

Сообщение vg »

sobomax писал(а):Не изобретайте велосипед - используйте стандартные алгоритмы хеширования типа MD5. Там правда длина хеша - 16 байт то есть 32 hex символа, но можно спокойно взять только первых 16.

-Maxim
Чтобы спокойно взять, надо иметь доказательство, что любая 64 битная последовательность часть 128 битного хеша MD5 являтется однозначным отображением хешируемого значения. Упоминания такого уникального свойсва MD5 я не встречал. Впрочим сейчас так и сделал. Дополнительно проверяю коллизии. Для "партнёров" это ОК, как оказалось.
vg
Маньяк
Сообщения: 2803
Зарегистрирован: 29 май 2003, 22:29
Откуда: Магадан - Миссиссага

Сообщение vg »

Marmot писал(а):
sobomax писал(а):Не изобретайте велосипед - используйте стандартные алгоритмы хеширования типа MD5. Там правда длина хеша - 16 байт то есть 32 hex символа, но можно спокойно взять только первых 16.
А если сделать custom base64 0-9,a-Z,A-Z,_. то можно и ещё больше битиков в 16 символов напихать.

PS
Кстати, вот подумал, а если просто использовать timestamp в миллисекундах.
Это как раз 8 байтов, не думаю что вы генерите документы с частотой большей, чем разрешение системного таймера.
Даже если документы генерятся на нескольких машинах вероятность коллизии достаточно мала.
Про кастом base64. Идея не нова. Используется в кодировании URL. Другая идея (не моя я а профи), если сгенирировать по GUID MD5, а затем создать свой 256 литерный алфавит. Тогда можно отображать MD5 на допустимые XML и common ПО символы.

Про real8 для времени. В принципе хорошая идея. При этом, если отсчёт вести от 2000 года и на, скажем, 20 лет вперёд (долшьше не доживём), то появится место под дополнительные символы, типа:
IBMzczccfsdfds
Аватара пользователя
sobomax
Маньяк
Сообщения: 3699
Зарегистрирован: 29 июн 2006, 22:53
Откуда: Vancouver

Сообщение sobomax »

vg писал(а):
sobomax писал(а):Не изобретайте велосипед - используйте стандартные алгоритмы хеширования типа MD5. Там правда длина хеша - 16 байт то есть 32 hex символа, но можно спокойно взять только первых 16.

-Maxim
Чтобы спокойно взять, надо иметь доказательство, что любая 64 битная последовательность часть 128 битного хеша MD5 являтется однозначным отображением хешируемого значения. Упоминания такого уникального свойсва MD5 я не встречал. Впрочим сейчас так и сделал. Дополнительно проверяю коллизии. Для "партнёров" это ОК, как оказалось.
Никто не говорит что оно однозначное. Но предполагая равномерное распределение значений хеша, при скорости выборки 1000 значений в секунду потребуется почти 600 миллионов лет чтобы "поймать" коллизию. Боюсь не доживем. :lol:

(2**64)/(1000*60*60*24*365)

-Maxim
Последний раз редактировалось sobomax 07 сен 2006, 16:17, всего редактировалось 1 раз.
vg
Маньяк
Сообщения: 2803
Зарегистрирован: 29 май 2003, 22:29
Откуда: Магадан - Миссиссага

Сообщение vg »

dima писал(а):Сгенерируй GUID, перевери его в строку и посчитай MD5 этой строки.
Длина такой строки в XML будет равна 32 литерам в base16.
vg
Маньяк
Сообщения: 2803
Зарегистрирован: 29 май 2003, 22:29
Откуда: Магадан - Миссиссага

Сообщение vg »

sobomax писал(а): ... Но предполагая равномерное распределение значений...
Ню - ню :)
Аватара пользователя
sobomax
Маньяк
Сообщения: 3699
Зарегистрирован: 29 июн 2006, 22:53
Откуда: Vancouver

Сообщение sobomax »

vg писал(а):
sobomax писал(а): ... Но предполагая равномерное распределение значений...
Ню - ню :)
Мы живем в мире в котором вероятность является одной из объективных характеристик. Не я сказал.

А если серьезно то вы никогда не читали паспортные характеристики скажем винчестеров? Там в них совершенно четко прописаны вероятностные характеристики прочитать неверное значение с совершенно исправного устройства. Аналогично с любыми каналами передачи данных. Так что вероятность поиметь коллизию один раз в 600 миллионов лет может оказаться вовсе не самым слабым звеном.

-Maxim
Ответить