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

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

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

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

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

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

@miyvir · 10.02.2013, 11:46

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

Код

add a0, b0
adc a1, b1
...
adc an, bn

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

Код

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 бита результата.

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

Код

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 будет выглядеть так:

Код

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), там есть практически все на основе чего можно сделать математику для любых разрядностей.
И попутно можно еще заглянуть и сюда, там мало, но кое что есть.

@yr0407 0 / 0 / 0 Регистрация: 31.10.2012 Сообщений: 51
	12.02.2013, 03:30	14
	Сообщение от pmdr_soft Понадобилось оперировать 128 битными целыми числами. +,-,/,*. Есть какая то джедайская техника ? Как освоить по быстрому ? Ну если по быстрому то я бы начал вот отсюда -> 32 BIT MATH (AVR XXX), там есть практически все на основе чего можно сделать математику для любых разрядностей. И попутно можно еще заглянуть и сюда, там мало, но кое что есть. 0

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

@miyvir 0 / 0 / 0 Регистрация: 27.06.2010 Сообщений: 405
	10.02.2013, 11:46	2
	Сложение и вычитание делается просто. Ассемблерная функция (или вставка) по типу: Код add a0, b0 adc a1, b1 ... adc an, bn Можно в цикле сделать, можно развернуть, сделать линейный код. С умножением и особенно делением сложнее. Есть такой умный дядька, Дональд Кнут зовут, так вот он уже давно придумал и описал в своих книжках алгоритмы быстрого умножения и деления для больших чисел. Можно там посмотреть: Д.Кнут Искусство программирования. Но он тяжеловато пишет, много формул. Есть еще одна замечательная книжка - Hoskirs Delight ("Алгоритмические трюки для программистов" по русски), в ней тоже есть искомое, в частности модифицированные алгоритмы Кнута. Но имеющиеся алгоритмы придётся сильно адаптировать, чтоб они хорошо работали на AVR, потому, что они рассчитаны на 32-х битный процессор. Вот например, алгоритм Кнута для умножения 32x32=>64 заточенный для AVR, имеющий аппаратное умножение 8х8=>16. В этой функции возвращается только старшие 32 бита результата. Код 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 тактов, если на ассемблере реализовывать. 0

@_pv 0 / 0 / 0 Регистрация: 06.06.2011 Сообщений: 2,514
	10.02.2013, 13:36	3
	Сообщение от miyvir Вот например, алгоритм Кнута для умножения 32x32=>64 заточенный для AVR, имеющий аппаратное умножение 8х8=>16. В этой функции возвращается только старшие 32 бита результата. интереса ради не проверяли чем будет ассемблерный листинг отличаться от: Код long a, b; long long c = a * b; ? 0

@miyvir 0 / 0 / 0 Регистрация: 27.06.2010 Сообщений: 405
	10.02.2013, 13:57	4
	Проверял. 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	5
	а подскажите чем отличается запись long от long long ? В чем фокус ? 0

@miyvir 0 / 0 / 0 Регистрация: 27.06.2010 Сообщений: 405
	10.02.2013, 19:10	6
	Сообщение от pmdr_soft а подскажите чем отличается запись long от long long ? В чем фокус ? long - это int32. long long - это int64. 0

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

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

@miyvir 0 / 0 / 0 Регистрация: 27.06.2010 Сообщений: 405
	10.02.2013, 20:41	9
	http://en.wikipedia.org/wiki/C_data_types Типа 128 бит с стандарте нет. Некоторые компиляторы, на некоторых платформах поддерживают тип __int128. Например gcc и MS VisualStudyo, когда генерят код для платформы x64. Так, что для AVR uint128_t будет выглядеть так: Код 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); 0

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

@miyvir 0 / 0 / 0 Регистрация: 27.06.2010 Сообщений: 405
	11.02.2013, 10:29	11
	Сообщение от sohbtixhuk 128 бит RSA ключики - это уже немного не для AVR. Ну почему-же. Есть такие RSA security token generator. Генерирует одноразовый пароль на основе текущего времени, пин кода и 128 битного RSA ключа. <Изображение удалено> Я расковыривал такую штуку - нижняя слева на картинке. Там 8-ми битный Friiscale-овский процессор, RTC и питается всё от литиевой батарейки. Работает несколько лет, потом на выброс. 0

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

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