Реализация генератора уникальных идентификаторов

Тарасов А.Е., Кузнецов В.Е.

В повседневной работе обнаружилось, что все документы, передаваемые в государственные органы в процессе электронного документооборота должны иметь внутри поле с уникальным идентификатором. В качестве такового госорганы используют GUID.


Цитата из «Википедия»:

GUID (Globally Unique Identifier) — статистически уникальный 128-битный идентификатор. Его главная особенность — уникальность, которая позволяет создавать расширяемые сервисы и приложения без опасения конфликтов, вызванных совпадением идентификаторов. Хотя уникальность каждого отдельного GUID не гарантируется, общее количество уникальных ключей настолько велико (2128 или 3,4028×1038), что вероятность того, что в мире будут независимо сгенерированы два совпадающих ключа, крайне мала.

«GUID» называют некоторые реализации стандарта, имеющего название Universally Unique Identifier (UUID).

В тексте GUID записывается в виде строки из тридцати двух шестнадцатеричных цифр, разбитой на группы дефисами и окружённой фигурными скобками:

{6F9619FF-8B86-D011-B42D-00CF4FC964FF}


Поиск существующих библиотек по работе с GUID на языке программирования Rexx не дал результата. Анализ описания различных алгоритмов генерации для других языков программирования позволил сделать следующие выводы:

  • В большинстве языков программирования функция работы с GUID либо встроенные, либо входят в стандартные библиотеки.
  • Единого алгоритма генерации GUID не существует.
  • Существующие методики генерации можно условно разделить на две группы: в которых генерируется полностью случайная строка (такой подход встречается довольно часто), и где в качестве основы для генерации части цифр используют текущую дату, время, MAC адрес сетевой карточки и другие уникальные данные. Примерная структура GUID для этой группы описывается следующим образом:
typedef struct _GUID{

   unsigned long   Data1;

   unsigned short  Data2;

   unsigned short  Data3;

   unsigned char   Data4[8];} GUID;

Правая часть предоставляет собой шести байтовый MAC-адрес сетевой карты, а если её нет — то случайная последовательность. Следующие два байта тоже как-то связаны с оборудованием.

  • Определить, каким именно алгоритмом пользуется та или иная конкретная реализация функции, обычно невозможно.

Подробнее об особенностях различных алгоритмов можно посмотреть здесь:

Беря всё вышесказанное можно сделать вывод, что бессмысленно использовать извращенные алгоритмы генерацией GUID с использование в качестве основы для генерации части цифр текущую дату, время, MAC адреса и др. Так как несмотря та то, что для используемого алгоритма каждый GIUD будет уникален, нет ни каких гарантий, что такой же GUID не будет получен случайно на другом языке программирования.

Поэтому было принято решение использовать алгоритм с генерацией полностью случайного GUID, так как он проще в реализации при приемлемых результатах.

Ещё одной особенность при работе с госорганами является то, что они требуют использовать некую 4-тую версию GUID. Отличается она тем, что третий блок цифр начинается с цифры 4.

В результате был написан такой вариант реализации функции:

GUID:

return S4()S4()"-"S4()"-4"left(S4(),3)"-"S4()"-"S4()S4()S4()

s4:

return left(substr(d2x(((1+(random()/10))*d2x(10000))),2),4,0)

Итоговый результат меня вполне устраивает. Госорганы – тоже.

В процессе поиска решения генерации GUID, попалось несколько упоминаний, что его используют как уникальный идентификатор в базах данных, эта информация меня заинтересовала. Так же пришла идея использовать GUID в составных именах переменных. Но в классическом виде GIUD содержит знак «-» (минус), что не позволяет использовать его в этом качестве. Значит, придется отказаться от этого разделителя. Так же мне не понравилось, что размер строки слишком большой.

Для генераций уникальной в теории строки был выбран следующий формат:

CRC32(информационной строки) || ужатые дата и время || 4 случайных шестнадцатеричных цифры.

Для уменьшения длины строки применяем сжатие даты и времени по следующему алгоритму:

  • Год в формате BORNDATE * 86400+число секунд, истёкших после полуночи
  • Получившуюся строку переводим в шестнадцатеричный вид и берем 7 правых символов.

где:

Формат BORNDATE — это количество полных дней (не включая текущий день), начиная от даты рождества Христова (Январь 1, 0001), включая её.

86400 — десятичное количество секунд в сутках.

Данная схема гарантирует высокую неповторяемость в течение 8,5 лет и очень хорошую неповторяемость значительно дольше. Под высокой неповторяемостью следует понимать полную невозможность получить в последовательных запусках функции реже раза в секунду одинаковые результаты и хорошую неповторяемость при нарушении этого ограничения.

Для подсчета CRC32 передаваемой строки для универсальности воспользуемся функцией, самостоятельно написанной на REXX. При желании можно её заменить на такую же или другую функцию из соответствующей библиотеки, чем поднять скорость работы всего генератора уникальной строки. Но тогда получается привязка к библиотеке, что потенциально ухудшает переносимость программы под другие ОС.

После получения уникальной строки ужимаем её до 16 символов, путем выкидывания части незначащих бит. Это делается способом, несколько похожим на UUE кодирование. Как известно, в байте, содержащем символ шестнадцатиричной цифры, содержится 8 бит, но значение из них имеют только 4 (ведь различных шестнадцатиричных цифр только 16). Если изъять каким либо способом из цепочки незначащие (жировые) биты, длина строки уменьшится, однако в ней будут содержаться более разнообразные, чем шестнадцатиричные, символы (возможно и непечатные). Если ограничить допустимый выходной набор символов 32, 64 или другим числом, кратным 2 и большим 16, то можно, ужав не все жировые биты, сократить полученную строку. При наборе в 32 символа сжатие происходит на 20-25%, при 64 — чуть хуже 1.5 раз и т.д. Такие преобразования при взаимно различных символах кодирующего набора принципиально обратимы и могут сохранять алфавитный порядок строк при возрастающих значениях кодов символов набора.

В приведенной функции UCOD (см. ниже) для кодирования выбран набор из 32 различных печатных знаков.

Если увеличить строку в команде SubStr() до 64 знаков, заменив Left(UCOD,5,’1′) на Left(UCOD,6,’1′) и SubStr(UCOD,6) на SubStr(UCOD,7) можно поднять степень сжатия до примерно 1.5, но это потребует использования русских букв.

Если увеличить строку в команде SubStr() до 128 знаков, заменив Left(UCOD,5,’1′) на Left(UCOD,7,’1′) и SubStr(UCOD,6) на SubStr(UCOD,8) можно поднять степень сжатия ещё выше, но это уже потребует использование как заглавных, так и прописных букв.

Для того что бы возвращаемую уникальную строку можно было использовать в составном имени переменной REXX, первый символ такой строки всегда должен быть буквой. Это обеспечивается подставкой единицы в начале строки при преобразовании в двоичный вид.

В случае, когда генерация уникальной строки необходима не часто (не чаще раза в пару минут) можно использовать укороченный размер уникальной строки — 9 символов. Для этого не нужно передавать в функцию строку для получения CRC32, и эта часть строки будет опущена. А даты и времени с 4 случайными цифрами будет достаточно для генерации действительно случайной строки.

В результате проведенной работы были получены две функции генерации уникальных идентификаторов, одна из которых подходит для формирования документов для общения с госорганами, а вторую можно широко использовать в различных алгоритмах при программировании на REXX.

UCOD: Procedure

   NUMERIC DIGITS 12

   if arg(1)='' then UCOD=''

   else UCOD=CRC32Str(Arg(1))

   UCOD=UCOD||right(d2x(Date('B')*86400+Time('S')),7)||right(d2x(random(,255)),2,0)||right(d2x(random(,255)),2,0)

   S=''

   UCOD='1'X2B(UCOD)

   Do Until Length(UCOD)=0

      S=S''SubStr('0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ',X2D(B2X(Left(UCOD,5,'1')))+1,1)

      UCOD=SubStr(UCOD,6)

   End /* Until */

return S

CRC32Str: Procedure

   CRC32DAT.0=256

   CRC32DAT.1=00000000; CRC32DAT.2=77073096; CRC32DAT.3=ee0e612c; CRC32DAT.4=990951ba; CRC32DAT.5=076dc419; CRC32DAT.6=706af48f; CRC32DAT.7=e963a535; CRC32DAT.8=9e6495a3;

   CRC32DAT.9=0edb8832; CRC32DAT.10=79dcb8a4; CRC32DAT.11=e0d5e91e; CRC32DAT.12=97d2d988; CRC32DAT.13=09b64c2b; CRC32DAT.14=7eb17cbd; CRC32DAT.15=e7b82d07; CRC32DAT.16=90bf1d91;

   CRC32DAT.17=1db71064; CRC32DAT.18=6ab020f2; CRC32DAT.19=f3b97148; CRC32DAT.20=84be41de; CRC32DAT.21=1adad47d; CRC32DAT.22=6ddde4eb; CRC32DAT.23=f4d4b551; CRC32DAT.24=83d385c7;

   CRC32DAT.25=136c9856; CRC32DAT.26=646ba8c0; CRC32DAT.27=fd62f97a; CRC32DAT.28=8a65c9ec; CRC32DAT.29=14015c4f; CRC32DAT.30=63066cd9; CRC32DAT.31=fa0f3d63; CRC32DAT.32=8d080df5;

   CRC32DAT.33=3b6e20c8; CRC32DAT.34=4c69105e; CRC32DAT.35=d56041e4; CRC32DAT.36=a2677172; CRC32DAT.37=3c03e4d1; CRC32DAT.38=4b04d447; CRC32DAT.39=d20d85fd; CRC32DAT.40=a50ab56b;

   CRC32DAT.41=35b5a8fa; CRC32DAT.42=42b2986c; CRC32DAT.43=dbbbc9d6; CRC32DAT.44=acbcf940; CRC32DAT.45=32d86ce3; CRC32DAT.46=45df5c75; CRC32DAT.47=dcd60dcf; CRC32DAT.48=abd13d59;

   CRC32DAT.49=26d930ac; CRC32DAT.50=51de003a; CRC32DAT.51=c8d75180; CRC32DAT.52=bfd06116; CRC32DAT.53=21b4f4b5; CRC32DAT.54=56b3c423; CRC32DAT.55=cfba9599; CRC32DAT.56=b8bda50f;

   CRC32DAT.57=2802b89e; CRC32DAT.58=5f058808; CRC32DAT.59=c60cd9b2; CRC32DAT.60=b10be924; CRC32DAT.61=2f6f7c87; CRC32DAT.62=58684c11; CRC32DAT.63=c1611dab; CRC32DAT.64=b6662d3d;

   CRC32DAT.65=76dc4190; CRC32DAT.66=01db7106; CRC32DAT.67=98d220bc; CRC32DAT.68=efd5102a; CRC32DAT.69=71b18589; CRC32DAT.70=06b6b51f; CRC32DAT.71=9fbfe4a5; CRC32DAT.72=e8b8d433;

   CRC32DAT.73=7807c9a2; CRC32DAT.74=0f00f934; CRC32DAT.75=9609a88e; CRC32DAT.76=e10e9818; CRC32DAT.77=7f6a0dbb; CRC32DAT.78=086d3d2d; CRC32DAT.79=91646c97; CRC32DAT.80=e6635c01;

   CRC32DAT.81=6b6b51f4; CRC32DAT.82=1c6c6162; CRC32DAT.83=856530d8; CRC32DAT.84=f262004e; CRC32DAT.85=6c0695ed; CRC32DAT.86=1b01a57b; CRC32DAT.87=8208f4c1; CRC32DAT.88=f50fc457;

   CRC32DAT.89=65b0d9c6; CRC32DAT.90=12b7e950; CRC32DAT.91=8bbeb8ea; CRC32DAT.92=fcb9887c; CRC32DAT.93=62dd1ddf; CRC32DAT.94=15da2d49; CRC32DAT.95=8cd37cf3; CRC32DAT.96=fbd44c65;

   CRC32DAT.97=4db26158; CRC32DAT.98=3ab551ce; CRC32DAT.99=a3bc0074; CRC32DAT.100=d4bb30e2; CRC32DAT.101=4adfa541; CRC32DAT.102=3dd895d7; CRC32DAT.103=a4d1c46d; CRC32DAT.104=d3d6f4fb;

   CRC32DAT.105=4369e96a; CRC32DAT.106=346ed9fc; CRC32DAT.107=ad678846; CRC32DAT.108=da60b8d0; CRC32DAT.109=44042d73; CRC32DAT.110=33031de5; CRC32DAT.111=aa0a4c5f; CRC32DAT.112=dd0d7cc9;

   CRC32DAT.113=5005713c; CRC32DAT.114=270241aa; CRC32DAT.115=be0b1010; CRC32DAT.116=c90c2086; CRC32DAT.117=5768b525; CRC32DAT.118=206f85b3; CRC32DAT.119=b966d409; CRC32DAT.120=ce61e49f;

   CRC32DAT.121=5edef90e; CRC32DAT.122=29d9c998; CRC32DAT.123=b0d09822; CRC32DAT.124=c7d7a8b4; CRC32DAT.125=59b33d17; CRC32DAT.126=2eb40d81; CRC32DAT.127=b7bd5c3b; CRC32DAT.128=c0ba6cad;

   CRC32DAT.129=edb88320; CRC32DAT.130=9abfb3b6; CRC32DAT.131=03b6e20c; CRC32DAT.132=74b1d29a; CRC32DAT.133=ead54739; CRC32DAT.134=9dd277af; CRC32DAT.135=04db2615; CRC32DAT.136=73dc1683;

   CRC32DAT.137=e3630b12; CRC32DAT.138=94643b84; CRC32DAT.139=0d6d6a3e; CRC32DAT.140=7a6a5aa8; CRC32DAT.141=e40ecf0b; CRC32DAT.142=9309ff9d; CRC32DAT.143=0a00ae27; CRC32DAT.144=7d079eb1;

   CRC32DAT.145=f00f9344; CRC32DAT.146=8708a3d2; CRC32DAT.147=1e01f268; CRC32DAT.148=6906c2fe; CRC32DAT.149=f762575d; CRC32DAT.150=806567cb; CRC32DAT.151=196c3671; CRC32DAT.152=6e6b06e7;

   CRC32DAT.153=fed41b76; CRC32DAT.154=89d32be0; CRC32DAT.155=10da7a5a; CRC32DAT.156=67dd4acc; CRC32DAT.157=f9b9df6f; CRC32DAT.158=8ebeeff9; CRC32DAT.159=17b7be43; CRC32DAT.160=60b08ed5;

   CRC32DAT.161=d6d6a3e8; CRC32DAT.162=a1d1937e; CRC32DAT.163=38d8c2c4; CRC32DAT.164=4fdff252; CRC32DAT.165=d1bb67f1; CRC32DAT.166=a6bc5767; CRC32DAT.167=3fb506dd; CRC32DAT.168=48b2364b;

   CRC32DAT.169=d80d2bda; CRC32DAT.170=af0a1b4c; CRC32DAT.171=36034af6; CRC32DAT.172=41047a60; CRC32DAT.173=df60efc3; CRC32DAT.174=a867df55; CRC32DAT.175=316e8eef; CRC32DAT.176=4669be79;

   CRC32DAT.177=cb61b38c; CRC32DAT.178=bc66831a; CRC32DAT.179=256fd2a0; CRC32DAT.180=5268e236; CRC32DAT.181=cc0c7795; CRC32DAT.182=bb0b4703; CRC32DAT.183=220216b9; CRC32DAT.184=5505262f;

   CRC32DAT.185=c5ba3bbe; CRC32DAT.186=b2bd0b28; CRC32DAT.187=2bb45a92; CRC32DAT.188=5cb36a04; CRC32DAT.189=c2d7ffa7; CRC32DAT.190=b5d0cf31; CRC32DAT.191=2cd99e8b; CRC32DAT.192=5bdeae1d;

   CRC32DAT.193=9b64c2b0; CRC32DAT.194=ec63f226; CRC32DAT.195=756aa39c; CRC32DAT.196=026d930a; CRC32DAT.197=9c0906a9; CRC32DAT.198=eb0e363f; CRC32DAT.199=72076785; CRC32DAT.200=05005713;

   CRC32DAT.201=95bf4a82; CRC32DAT.202=e2b87a14; CRC32DAT.203=7bb12bae; CRC32DAT.204=0cb61b38; CRC32DAT.205=92d28e9b; CRC32DAT.206=e5d5be0d; CRC32DAT.207=7cdcefb7; CRC32DAT.208=0bdbdf21;

   CRC32DAT.209=86d3d2d4; CRC32DAT.210=f1d4e242; CRC32DAT.211=68ddb3f8; CRC32DAT.212=1fda836e; CRC32DAT.213=81be16cd; CRC32DAT.214=f6b9265b; CRC32DAT.215=6fb077e1; CRC32DAT.216=18b74777;

   CRC32DAT.217=88085ae6; CRC32DAT.218=ff0f6a70; CRC32DAT.219=66063bca; CRC32DAT.220=11010b5c; CRC32DAT.221=8f659eff; CRC32DAT.222=f862ae69; CRC32DAT.223=616bffd3; CRC32DAT.224=166ccf45;

   CRC32DAT.225=a00ae278; CRC32DAT.226=d70dd2ee; CRC32DAT.227=4e048354; CRC32DAT.228=3903b3c2; CRC32DAT.229=a7672661; CRC32DAT.230=d06016f7; CRC32DAT.231=4969474d; CRC32DAT.232=3e6e77db;

   CRC32DAT.233=aed16a4a; CRC32DAT.234=d9d65adc; CRC32DAT.235=40df0b66; CRC32DAT.236=37d83bf0; CRC32DAT.237=a9bcae53; CRC32DAT.238=debb9ec5; CRC32DAT.239=47b2cf7f; CRC32DAT.240=30b5ffe9;

   CRC32DAT.241=bdbdf21c; CRC32DAT.242=cabac28a; CRC32DAT.243=53b39330; CRC32DAT.244=24b4a3a6; CRC32DAT.245=bad03605; CRC32DAT.246=cdd70693; CRC32DAT.247=54de5729; CRC32DAT.248=23d967bf;

   CRC32DAT.249=b3667a2e; CRC32DAT.250=c4614ab8; CRC32DAT.251=5d681b02; CRC32DAT.252=2a6f2b94; CRC32DAT.253=b40bbe37; CRC32DAT.254=c30c8ea1; CRC32DAT.255=5a05df1b; CRC32DAT.256=2d02ef8d;

   CRC=X2C('FFFFFFFF')

   do n=1 to length(ARG(1))

      I=C2D(BitXor(Right(CRC,1),substr(ARG(1),n,1)))+1

      CRC=BitXor(X2C(CRC32dat.I),X2C('0')''Left(CRC,3))

   end /* do n */

   CRC=C2X(BitXor(CRC,X2C('FFFFFFFF')))

Return CRC

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *