Никак не могу найти описание алгортма генерации UUID (или как их еще называют GUID). Вроде это дело стандартизованно и даже описывается ISO/IEC 11578:1996, но найти в свободном доступе текст этого стандарта, не удалось.
Хотелось бы описание алгоритма для

• Time-based UUID
• DCE security UUID
• Name-based UUID
• Randomly generated UUID

В линуксах используется генерация GUID на базе MAC адреса.
Можно глянуть исходняки libuuid.so
UUID не то же, что и GUID. UUID уникален в текущий момент на конкретной машине.
GUID - уникален абсолютно.

Цитата(LSD @ 4.8.2005, 13:51)

Time-based UUID

Банальная генерация от системного времени (дата, время, микросекунды).

Цитата(LSD @ 4.8.2005, 13:51)

Randomly generated UUID

Просто рэндомим. Либо на авось, либо имеем хранилище созданных UUID'ов

Про остальные не скажу, но они не дают абсолютной уникальности.
Также бывает банальная инкрементная генерация.

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

Меня интересует именно описание алгоритма, расписанное до бит, в каком бите что хранится. Там ведь есть вполне конкретный формат:

Цитата

There exist different variants of these global identifiers. The methods of this class are for manipulating the Leach-Salz variant, although the constructors allow the creation of any variant of UUID (described below). The layout of a variant 2 (Leach-Salz) UUID is as follows: The most significant long consists of the following unsigned fields: 0xFFFFFFFF00000000 time_low 0x00000000FFFF0000 time_mid 0x000000000000F000 version 0x0000000000000FFF time_hi The least significant long consists of the following unsigned fields: 0xC000000000000000 variant 0x3FFF000000000000 clock_seq 0x0000FFFFFFFFFFFF node The variant field contains a value which identifies the layout of the UUID. The bit layout described above is valid only for a UUID with a variant value of 2, which indicates the Leach-Salz variant. The version field holds a value that describes the type of this UUID. There are four different basic types of UUIDs: time-based, DCE security, name-based, and randomly generated UUIDs. These types have a version value of 1, 2, 3 and 4, respectively.

вот описание остальных форматов я и ищу, особенно интересует формат с использованием MAC адреса.

Могу предложить только линуксовые исходняки на C:
http://cvs.opensolaris.org/source/xref/usr...libuuid/common/
и
http://devel.santafelinux.com/source/scrol...0.3.14/libuuid/

Виндовых исходняком, естественно, дать не могу.

А зачем тебе это вообще? Ведь GUIDы создаются стандартными средствами.
Или ты наоборот разобрать хочешь?

Мне надо написать свой генератор на Java. Там есть стандартный UUID, но он появился в JDK 1.5 и не использует MAC, а это крайне желательно.

Хм. Я конечно не большой спец по JAVA. Но сдается мне, что получить MAC адрес без встроенной поддержки VM не получится.
Если таковая все же имеется, то тогда нужно определиться со стандартом.
UUIDы бывают разной длины.
Учитывая, что интересует MAC генерация, полагаю, что тебе нужен именно GUID.
Если получить MAC реально, то можно написать код на базе линуксового.
Что касается готового кода, то нашел ветку с примером на сановском форуме:
http://forum.java.sun.com/thread.jspa?thre...ssageID=1031698
Там есть пример генерации 128битного GUIDa, но базирован на параметрах системы.
Это конечно не абсолютно Global UID, но как там сказано, достаточно близко к этому.

Цитата(Snowy @ 5.8.2005, 11:01)

Но сдается мне, что получить MAC адрес без встроенной поддержки VM не получится.

MAC адрес я уже научился получать, осталось только сгенерировать GUID с его использованием.

GUID на базе MAC выглядит примерно так:
Первые 8 байт это TimeStamp.
Причем последние полбайта - номер версии GUID'a = 1.
То есть сдвигаем TimeStamp на 4 бита и вписываем в них номер версии. (то есть еденичку)
Затем Идут 2 байта - счетчик.
То есть, если мы в один TimeStamp успеваем сгенерить несколько гуидов, то этот счетчик увеличивается. Если таймстамп перешагнул дальше, то сбрасываем.
Эти два байта также сдвигаем, но на 2 бита. Младшие 2 бита зарезервированы.
Последние 6 байт - просто MAC адрес.
Переводим в HEX, добавляем разделители. GUID готов.

Это базовый стандарт GUID первой версии.
Винда, похоже, просто берет данные, добавляет рэндом и конвертит по какому-то алгоритму, исключающему повтор при разных входных данных.
Как я уже говорил, реализация M$ мне недоступна.

Цитата(Snowy @ 5.8.2005, 16:19)

Винда, похоже, просто берет данные, добавляет рэндом и конвертит по какому-то алгоритму, исключающему повтор при разных входных данных.

Насколько я в курсе, при вычислении этих данных используется текущее время и дата, что теоретически гарантирует уникальность

Цитата(DENNN @ 5.8.2005, 16:36)

Насколько я в курсе, при вычислении этих данных используется текущее время и дата, что теоретически гарантирует уникальность

Если читал пост, то только об этом и говорится.
Я имею ввиду то, что у GUID'a сгенереного виндой, отсутсвуют фиксированные части.
Каждый раз GUID получается совершенно (а не чуть-чуть) разным.
Значит используется какой-то хитрый алгоритм, который так перемешивает входные данные.
Пример:
Стандартные GUID:
{00008F2C-72C1-0000-0000-8C8H92C09E12}
{00008F2C-72C1-0000-0008-8C8H92C09E12}
{00008F2D-72C1-0000-0000-8C8H92C09E12}
{00008F2D-72C1-0000-0010-8C8H92C09E12}
GUIDы винды:
{280936f3-6b32-4536-a99b-7b6cf95a0f0b}
{d19ce482-d817-4649-8da6-4dc2642c961c}
{0c54a729-d92f-477c-bea5-31b24ac1c59f}
{1b65a986-fce4-409d-8f35-0f2d4dae10f1}
Налицо явное отсутствие постоянной части.
Налицо отличие от стандарта первой версии.
Да я вообще не знаю, как он устроен.
У него даже поле версии всегда разное.
Сплошной рэндом какой-то.

Цитата(Snowy @ 5.8.2005, 18:22)

Я имею ввиду то, что у GUID'a сгенереного виндой, отсутсвуют фиксированные части.

На самом деле они присутсвуют, это:
{XXXXXXX-XXXX-4XXX-AXXX-XXXXXXXXXXXX}
вместо A может быть 8, 9, A, B.

А вообще я нашел спецификацию. Всем спасибо за помощь!

Присоединённый файл ( Кол-во скачиваний: 41 )
 draft_leach_uuids_guids_01.zip 15,71 Kb

Цитата(DENNN @ 5.8.2005, 16:36)

Насколько я в курсе, при вычислении этих данных используется текущее время и дата, что теоретически гарантирует уникальность

А вот скажите мне, как в системах, основанных на Timestamp, решается вопрос с переходом на зимнее время (то есть когда стрелка переводится назад)? Ведь при этом в течение целого часа будет существовать возможность генерации дубликатных ID.

Теоретически можно использовать счетчик, как описал Snowy, но тогда нужно будет хранить довольно таки здоровый мап из ID, сгенерированных за последний час, да еще как-то чистить его асинхронным образом (впрочем, можно и синхронным, но может быть немножко накладно).

Кто как думает?

Цитата(Stampede @ 5.8.2005, 22:48)

А вот скажите мне, как в системах, основанных на Timestamp, решается вопрос с переходом на зимнее время (то есть когда стрелка переводится назад)?

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

Цитата(LSD @ 5.8.2005, 21:55)

Во первых там используется GMT, а во вторых используется инкрементальный счетчик.

Само по себе использование GMT не решает проблему перевода времени "взад", как в случае с переходом на зимнее время. А счетчик, выходит, действительно используется, и при этом не совсем так, как написал Snowy.

Цитата

If the clock is set backwards, or even might have been set backwards (e.g., while the system was powered off), and the UUID generator can not be sure that no UUIDs were generated with timestamps larger than the value to which the clock was set, then the clock sequence has to be changed. If the previous value of the clock sequence is known, it can be just incremented; otherwise it should be set to a random or high-quality pseudo random value. ... The clock sequence MUST be originally (i.e., once in the lifetime of a system) initialized to a random number to minimize the correlation across systems.

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

Вопрос только, как узнать, что время было переведено назад? А, понял: в ходе сессии хранить только самый последний Timestamp, и сравнивать с текущим временем при каждом новом обращении к генератору, а при каждом рестарте системы иницииализироватьрвать заново.

Цитата(LSD @ 5.8.2005, 13:02)

MAC адрес я уже научился получать

Кстати, а как получил?

Цитата(Stampede @ 5.8.2005, 23:15)

Само по себе использование GMT не решает проблему перевода времени "взад", как в случае с переходом на зимнее время.

В GMT нет понятия зимнего/летнего времени.

Цитата(Stampede @ 5.8.2005, 23:15)

Кстати, а как получил?

ipconfig /all
и
ifconfig
а дальше парсинг stdout