Работа с 128 битными числами

@pmdr_soft · Регистрация: 15.03.2010

Студворк — интернет-сервис помощи студентам

Делаю генерацию ключей для RSA.
Контроллер atmega644p.

Понадобилось оперировать 128 битными целыми числами. +,-,/,*.

Есть какая то джедайская техника ? Как освоить по быстрому ?

@miyvir · 10.02.2013, 11:46

Сложение и вычитание делается просто. Ассемблерная функция (или вставка) по типу:

Code
1
2
3
4
add a0, b0
adc a1, b1
...
adc an, bn

Можно в цикле сделать, можно развернуть, сделать линейный код.
С умножением и особенно делением сложнее. Есть такой умный дядька, Дональд Кнут зовут, так вот он уже давно придумал и описал в своих книжках алгоритмы быстрого умножения и деления для больших чисел. Можно там посмотреть: Д.Кнут Искусство программирования. Но он тяжеловато пишет, много формул.
Есть еще одна замечательная книжка - Hoskirs Delight ("Алгоритмические трюки для программистов" по русски), в ней тоже есть искомое, в частности модифицированные алгоритмы Кнута. Но имеющиеся алгоритмы придётся сильно адаптировать, чтоб они хорошо работали на AVR, потому, что они рассчитаны на 32-х битный процессор.
Вот например, алгоритм Кнута для умножения 32x32=>64 заточенный для AVR, имеющий аппаратное умножение 8х8=>16. В этой функции возвращается только старшие 32 бита результата.

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
static inline uint32_t mul32hu(uint32_t u, uint32_t v)
{
uint8_t a0 = (uint8_t)(u >> 0);
uint8_t a1 = (uint8_t)(u >> 8);
uint8_t a2 = (uint8_t)(u >> 16);
uint8_t a3 = (uint8_t)(u >> 24);
 
uint8_t b0 = (uint8_t)(v >> 0);
uint8_t b1 = (uint8_t)(v >> 8);
uint8_t b2 = (uint8_t)(v >> 16);
uint8_t b3 = (uint8_t)(v >> 24);
 
union
{
struct
{
uint8_t w0, w1, w2, w3, w4, w5, w6, w7;
} u8;
uint32_t u32[2];
};
 
u8.w0 = u8.w1 = u8.w2 = u8.w3 = u8.w4 = u8.w5 = u8.w6 = u8.w7 = 0;
 
uint8_t k = 0;
uint16_t t;
 
t = a0 * b0 + u8.w0 + k;   u8.w0 = t;   k = t >> 8;
t = a1 * b0 + u8.w1 + k;   u8.w1 = t;   k = t >> 8;
t = a2 * b0 + u8.w2 + k;   u8.w2 = t;   k = t >> 8;
t = a3 * b0 + u8.w3 + k;   u8.w3 = t;   k = t >> 8;
u8.w4 = k;   k = 0;
 
t = a0 * b1 + u8.w1 + k;   u8.w1 = t;   k = t >> 8;
t = a1 * b1 + u8.w2 + k;   u8.w2 = t;   k = t >> 8;
t = a2 * b1 + u8.w3 + k;   u8.w3 = t;   k = t >> 8;
t = a3 * b1 + u8.w4 + k;   u8.w4 = t;   k = t >> 8;
u8.w5 = k;   k = 0;
 
t = a0 * b2 + u8.w2 + k;   u8.w2 = t;   k = t >> 8;
t = a1 * b2 + u8.w3 + k;   u8.w3 = t;   k = t >> 8;
t = a2 * b2 + u8.w4 + k;   u8.w4 = t;   k = t >> 8;
t = a3 * b2 + u8.w5 + k;   u8.w5 = t;   k = t >> 8;
u8.w6 = k;   k = 0;
 
t = a0 * b3 + u8.w3 + k;   u8.w3 = t;   k = t >> 8;
t = a1 * b3 + u8.w4 + k;   u8.w4 = t;   k = t >> 8;
t = a2 * b3 + u8.w5 + k;   u8.w5 = t;   k = t >> 8;
t = a3 * b3 + u8.w6 + k;   u8.w6 = t;   k = t >> 8;
u8.w7 = k;
 
return u32[1];
}

По этому алгоритму умножение 128-ми битных чисел, я могу оценить примерно в 2000 тактов процессора.
Деление скорее всего придётся делать сдвигами и вычитаниями, так как аппаратного деление нет никакого и алгоритм кнута выигрыша не даст. Получится примерно 5000 - 10000 тактов, если на ассемблере реализовывать.

@_pv · 10.02.2013, 13:36

Сообщение от miyvir

Вот например, алгоритм Кнута для умножения 32x32=>64 заточенный для AVR, имеющий аппаратное умножение 8х8=>16. В этой функции возвращается только старшие 32 бита результата.

интереса ради не проверяли чем будет ассемблерный листинг отличаться от:

Code
1
2
long a, b;
long long c = a * b;

?

@miyvir · 10.02.2013, 13:57

Проверял.
1) в выражении a * b не будет автоматически происходить расширения до long long. Результат будет 32-х разрядным. Надо так: long long c = (long long)a * b;
2) В avr-gcc это умножение реализовано сдвигами и сложениями без использования аппаратного умножения. Как результат, тот код, что я привёл выполняется за время около 100 тактов, встроенное умножение - около 700-800 тактов (пишу по пямяти, могу наврать).

@pmdr_soft · 10.02.2013, 18:00

а подскажите чем отличается запись long от long long ? В чем фокус ?

@miyvir · 10.02.2013, 19:10

Сообщение от pmdr_soft

а подскажите чем отличается запись long от long long ? В чем фокус ?

long - это int32.
long long - это int64.

@pmdr_soft · 10.02.2013, 20:00

а как будет 128 bit ? long long long long ? В чем нигия ?

Есть где то описание таких типов ?

@kysoft · 10.02.2013, 20:25

Вот здесь есть про long long long http://ru.wikipedia.org/wiki/Long,_Long,_Long
:) шучу, можно почитать, например, здесь: http://en.wikipedia.org/wiki/I... r_science)

@miyvir · 10.02.2013, 20:41

http://en.wikipedia.org/wiki/C_data_types
Типа 128 бит с стандарте нет. Некоторые компиляторы, на некоторых платформах поддерживают тип __int128. Например gcc и MS VisualStudyo, когда генерят код для платформы x64.
Так, что для AVR uint128_t будет выглядеть так:

Code
1
2
3
4
5
6
7
8
9
10
11
12
typedef struct
{
uint8_t bytes[16];
} uint128_t;
...
void add_uint128(const uint128_t *a, const uint128_t *b, uint128_t *result)
{
// Put your code here
}
...
uint128_t a = {...}, b = {...}, c;
add_uint128(&a, &b, &c);

@sohbtixhuk · 11.02.2013, 03:32

Прекратите насиловать лошадь. 128 бит RSA ключики - это уже немного не для AVR.
Не знаю, правда или нет, но вроде как DSP умеют довольно шустро перемалывать большие и нестандартные вещи

@miyvir · 11.02.2013, 10:29

Сообщение от sohbtixhuk

128 бит RSA ключики - это уже немного не для AVR.

Ну почему-же. Есть такие RSA security token generator. Генерирует одноразовый пароль на основе текущего времени, пин кода и 128 битного RSA ключа.

<Изображение удалено>
Я расковыривал такую штуку - нижняя слева на картинке. Там 8-ми битный Friiscale-овский процессор, RTC и питается всё от литиевой батарейки. Работает несколько лет, потом на выброс.

@pmdr_soft · 11.02.2013, 21:27

Помогите разобраться.

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

Помоги разобраться как этим пользоваться.

[9.53 Кб]

@pmdr_soft · 11.02.2013, 23:05

заработало вроде.

@yr0407 · 12.02.2013, 03:30

Сообщение от pmdr_soft

Понадобилось оперировать 128 битными целыми числами. +,-,/,*.
Есть какая то джедайская техника ? Как освоить по быстрому ?

Ну если по быстрому то я бы начал вот отсюда -> 32 BIT MATH (AVR XXX), там есть практически все на основе чего можно сделать математику для любых разрядностей.
И попутно можно еще заглянуть и сюда, там мало, но кое что есть.

Новые блоги и статьи Все статьи Все блоги /
И решил я переделать этот ноут в машину для распределенных вычислений Programma_Boinc 09.11.2025 И решил я переделать этот ноут в машину для распределенных вычислений Всем привет. А вот мой компьютер, переделанный из ноутбука. Был у меня ноут асус 2011 года. Со временем корпус превратился. . .	Мысли в слух kumehtar 07.11.2025 Заметил среди людей, что по-настоящему верная дружба бывает между теми, с кем нечего делить.	Новая зверюга volvo 07.11.2025 Подарок на Хеллоуин, и теперь у нас кроме Tuxedo Cat есть еще и щенок далматинца: Хочу еще Симбу взять, очень нравится. . .	Инференс ML моделей в Java: TensorFlow, DL4J и DJL Javaican 05.11.2025 Python захватил мир машинного обучения - это факт. Но когда дело доходит до продакшена, ситуация не так однозначна. Помню проект в крупном банке три года назад: команда data science натренировала. . .	Mapped types (отображённые типы) в TypeScript Reangularity 03.11.2025 Mapped types работают как конвейер - берут существующую структуру и производят новую по заданным правилам. Меняют модификаторы свойств, трансформируют значения, фильтруют ключи. Один раз описал. . .
Адаптивная случайность в Unity: динамические вероятности для улучшения игрового дизайна GameUnited 02.11.2025 Мой знакомый геймдизайнер потерял двадцать процентов активной аудитории за неделю. А виновником оказался обычный генератор псевдослучайных чисел. Казалось бы - добавил в карточную игру случайное. . .	Протоколы в Python py-thonny 31.10.2025 Традиционная утиная типизация работает просто: попробовал вызвать метод, получилось - отлично, не получилось - упал с ошибкой в рантайме. Протоколы добавляют сюда проверку на этапе статического. . .	C++26: Read-copy-update (RCU) bytestream 30.10.2025 Прошло почти двадцать лет с тех пор, как производители процессоров отказались от гонки мегагерц и перешли на многоядерность. И знаете что? Мы до сих пор спотыкаемся о те же грабли. Каждый раз, когда. . .	Изображения webp на старых x32 ОС Windows XP и Windows 7 Argus19 30.10.2025 Изображения webp на старых x32 ОС Windows XP и Windows 7 Чтобы решить задачу, использовал интернет: поисковики Google и Yandex, а также подсказки Deep Seek. Как оказалось, чтобы создать. . .	Passkey в ASP.NET Core identity stackOverflow 29.10.2025 Пароли мертвы. Нет, серьезно - я повторяю это уже лет пять, но теперь впервые за это время чувствую, что это не просто красивые слова. В . NET 10 команда Microsoft внедрила поддержку Passkey прямо в. . .

@pmdr_soft 0 / 0 / 0 Регистрация: 15.03.2010 Сообщений: 287

	Работа с 128 битными числами 10.02.2013, 08:39. Показов 9478. Ответов 13 Метки нет (Все метки) Делаю генерацию ключей для RSA. Контроллер atmega644p. Понадобилось оперировать 128 битными целыми числами. +,-,/,*. Есть какая то джедайская техника ? Как освоить по быстрому ? 0

@miyvir 0 / 0 / 0 Регистрация: 27.06.2010 Сообщений: 405
	10.02.2013, 13:57
	Проверял. 1) в выражении a * b не будет автоматически происходить расширения до long long. Результат будет 32-х разрядным. Надо так: long long c = (long long)a * b; 2) В avr-gcc это умножение реализовано сдвигами и сложениями без использования аппаратного умножения. Как результат, тот код, что я привёл выполняется за время около 100 тактов, встроенное умножение - около 700-800 тактов (пишу по пямяти, могу наврать). 0

@pmdr_soft 0 / 0 / 0 Регистрация: 15.03.2010 Сообщений: 287
	10.02.2013, 18:00
	а подскажите чем отличается запись long от long long ? В чем фокус ? 0

@pmdr_soft 0 / 0 / 0 Регистрация: 15.03.2010 Сообщений: 287
	10.02.2013, 20:00
	а как будет 128 bit ? long long long long ? В чем нигия ? Есть где то описание таких типов ? 0

@kysoft 0 / 0 / 0 Регистрация: 13.01.2013 Сообщений: 140
	10.02.2013, 20:25
	Вот здесь есть про long long long http://ru.wikipedia.org/wiki/Long,_Long,_Long :) шучу, можно почитать, например, здесь: http://en.wikipedia.org/wiki/I... r_science) 0

@sohbtixhuk 0 / 0 / 0 Регистрация: 14.02.2010 Сообщений: 798
	11.02.2013, 03:32
	Прекратите насиловать лошадь. 128 бит RSA ключики - это уже немного не для AVR. Не знаю, правда или нет, но вроде как DSP умеют довольно шустро перемалывать большие и нестандартные вещи 0

@pmdr_soft 0 / 0 / 0 Регистрация: 15.03.2010 Сообщений: 287
	11.02.2013, 21:27
	Помогите разобраться. Эти исходники позволяют вычитать, прибавлять, умножать, делить числа больших размерностей. Помоги разобраться как этим пользоваться. [9.53 Кб] 0

@pmdr_soft 0 / 0 / 0 Регистрация: 15.03.2010 Сообщений: 287
	11.02.2013, 23:05
	заработало вроде. 0

Опции темы