Форум программистов, компьютерный форум, киберфорум
Наши страницы
Микроконтроллеры Atmega AVR
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.69/42: Рейтинг темы: голосов - 42, средняя оценка - 4.69
pmdr_soft
0 / 0 / 0
Регистрация: 15.03.2010
Сообщений: 287
1

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

10.02.2013, 08:39. Просмотров 7727. Ответов 13
Метки нет (Все метки)

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

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

Есть какая то джедайская техника ? Как освоить по быстрому ?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.02.2013, 08:39
Ответы с готовыми решениями:

Проблема с 32 битными числами
Есть такой участок кода: uint32_t chostmoe = 0; uint8_t stepen; chostmoe += (1<<stepen); в...

Массив с отрицательными числами (Atmega 128, ASM)
Снова обращаюсь за помощью, не могу понять как реализовать данное задание Дан массив чисел N,...

Разработать класс или библиотеку функций для работы с m-битными целыми числами
Здравствуйте, кто-то знает как это реализовать? разработать класс или библиотеку функций для...

Работа с 16-битными оттенками серого
Здравствуйте. Какие средства в C++ позволяют работать с 16-битными оттенками серого?

Работа с 12-битными данными из бинарного файла
Устройство со своей 12-битной АЦП пишет на флешку бинарник с отсчетами по 12 бит, при этом ...

13
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,515
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
10.02.2013, 13:57
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/Integer_(somputer_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
Сообщений: 799
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
yr0407
0 / 0 / 0
Регистрация: 31.10.2012
Сообщений: 51
12.02.2013, 03:30 14
Цитата Сообщение от pmdr_soft
Понадобилось оперировать 128 битными целыми числами. +,-,/,*.
Есть какая то джедайская техника ? Как освоить по быстрому ?
Ну если по быстрому то я бы начал вот отсюда -> 32 BIT MATH (AVR XXX), там есть практически все на основе чего можно сделать математику для любых разрядностей.
И попутно можно еще заглянуть и сюда, там мало, но кое что есть.
0
12.02.2013, 03:30
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.02.2013, 03:30

Типы: почему если прибавить единицу к char, получится 128, а не -128?
Если мы прибавляем 1 к максимальному значению unsigned int - результат &quot;0&quot;. Тогда почему если...

SELECT запрос файла 128 мб, PHP скрипт отжимает эти 128 мб, можно ли сэкономить?
error_log(memory_get_peak_usage(true)); error_log(memory_get_usage(true)); Показывают, что...

Массив: Заполнить массив значениями от 0 до 255, если значение меньше 128, заменить на 0, больше 128 - на 1...
Задача: Заполнить двумерный массив значениями от 0 до 255. Если значение меньше 128, заменить на 0,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru