Как оптимизировать S-боксы CASUMI?

Я пытаюсь оптимизировать алгоритм Kasumi crypto, написанный на C. Есть S-box, который использует для шифрования данных. который я представляю, как массив, в котором огромно:Как оптимизировать S-боксы CASUMI?

int S7[128] = { 
    54, 50, 62, 56, 22, 34, 94, 96, 38, 6, 63, 93, 2, 18,123, 33, 
    55,113, 39,114, 21, 67, 65, 12, 47, 73, 46, 27, 25,111,124, 81, 
    53, 9,121, 79, 52, 60, 58, 48,101,127, 40,120,104, 70, 71, 43, 
    20,122, 72, 61, 23,109, 13,100, 77, 1, 16, 7, 82, 10,105, 98, 
    117,116, 76, 11, 89,106, 0,125,118, 99, 86, 69, 30, 57,126, 87, 
    112, 51, 17, 5, 95, 14, 90, 84, 91, 8, 35,103, 32, 97, 28, 66, 
    102, 31, 26, 45, 75, 4, 85, 92, 37, 74, 80, 49, 68, 29,115, 44, 
    64,107,108, 24,110, 83, 36, 78, 42, 19, 15, 41, 88,119, 59, 3 
}; 

int S9[512] = { 
    167,239,161,379,391,334, 9,338, 38,226, 48,358,452,385, 90,397, 
    183,253,147,331,415,340, 51,362,306,500,262, 82,216,159,356,177, 
    175,241,489, 37,206, 17, 0,333, 44,254,378, 58,143,220, 81,400, 
    95, 3,315,245, 54,235,218,405,472,264,172,494,371,290,399, 76, 
    165,197,395,121,257,480,423,212,240, 28,462,176,406,507,288,223, 
    501,407,249,265, 89,186,221,428,164, 74,440,196,458,421,350,163, 
    232,158,134,354, 13,250,491,142,191, 69,193,425,152,227,366,135, 
    344,300,276,242,437,320,113,278, 11,243, 87,317, 36, 93,496, 27, 
    487,446,482, 41, 68,156,457,131,326,403,339, 20, 39,115,442,124, 
    475,384,508, 53,112,170,479,151,126,169, 73,268,279,321,168,364, 
    363,292, 46,499,393,327,324, 24,456,267,157,460,488,426,309,229, 
    439,506,208,271,349,401,434,236, 16,209,359, 52, 56,120,199,277, 
    465,416,252,287,246, 6, 83,305,420,345,153,502, 65, 61,244,282, 
    173,222,418, 67,386,368,261,101,476,291,195,430, 49, 79,166,330, 
    280,383,373,128,382,408,155,495,367,388,274,107,459,417, 62,454, 
    132,225,203,316,234, 14,301, 91,503,286,424,211,347,307,140,374, 
    35,103,125,427, 19,214,453,146,498,314,444,230,256,329,198,285, 
    50,116, 78,410, 10,205,510,171,231, 45,139,467, 29, 86,505, 32, 
    72, 26,342,150,313,490,431,238,411,325,149,473, 40,119,174,355, 
    185,233,389, 71,448,273,372, 55,110,178,322, 12,469,392,369,190, 
    1,109,375,137,181, 88, 75,308,260,484, 98,272,370,275,412,111, 
    336,318, 4,504,492,259,304, 77,337,435, 21,357,303,332,483, 18, 
    47, 85, 25,497,474,289,100,269,296,478,270,106, 31,104,433, 84, 
    414,486,394, 96, 99,154,511,148,413,361,409,255,162,215,302,201, 
    266,351,343,144,441,365,108,298,251, 34,182,509,138,210,335,133, 
    311,352,328,141,396,346,123,319,450,281,429,228,443,481, 92,404, 
    485,422,248,297, 23,213,130,466, 22,217,283, 70,294,360,419,127, 
    312,377, 7,468,194, 2,117,295,463,258,224,447,247,187, 80,398, 
    284,353,105,390,299,471,470,184, 57,200,348, 63,204,188, 33,451, 
    97, 30,310,219, 94,160,129,493, 64,179,263,102,189,207,114,402, 
    438,477,387,122,192, 42,381, 5,145,118,180,449,293,323,136,380, 
    43, 66, 60,455,341,445,202,432, 8,237, 15,376,436,464, 59,461 
};

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

Любое предложение, чтобы оптимизировать это либо путем изменения этого массива на любую другую структуру данных?

источник

2013-11-28 RATHI

Почему функция заголовка и функции влияет на производительность кеша? –

Но FYI, если вы работаете на типичной 32-битной платформе, 'int' занимает вдвое больше места, чем вам действительно нужно. Вы можете сократить использование кэша вдвое, переключившись на 'int16_t'. –

Поместите s7 и s3 в один и тот же непрерывный массив, чтобы обеспечить пространственную локальность ссылки, может быть микрооптимизация – UmNyobe

этот массив не огромен. типичный кэш L1 составляет не менее 10 с кБ (это общая память, скажем, яблоко ii). и перемещение массива из заголовка в функцию не будет изменяться.

Сохранение его в соответствующей форме (как в комментариях) может иметь смысл (оно будет вписываться в кеш l1, но если у вас есть другие данные, возможно, используемые другим потоком, есть больше шансов остаться там) - есть нет необходимости в более чем 2 байтах на одно значение (но я не знаю, добавляет ли это дополнительные затраты по сравнению с использованием встроенных TS).

Если это действительно важно, вы должны посмотреть на генерируемый код и оптимизировать его.

источник

2013-11-28 12:08:34

Прежде всего, убедитесь, что вы объявили эти массивы как const, чтобы компилятор знал, что они никогда не изменятся.

Во-вторых, как предлагает Оли Чарлворт в комментариях, вам не нужен полный int для хранения каждого значения. Элементы S7 и S9 массивов 7-разрядные и 9-битные целые числа без знака, так что любой из int8_t или uint8_t должен быть достаточен для S7, и любое из int16_t или uint16_t для S9. (Вы можете бенчмарка, есть ли какая-то разница между использованием знаком или без знака типа, хотя я бы не ожидать каких-либо.)

Наконец, если вы действительно хотите избавиться от массивов полностью, это также возможно, для реализации S-боксов KASUMI непосредственно без любых таблиц поиска с использованием битовых операций (в частности, AND и XOR). Подробнее см. На стр. 13 – 16 из KASUMI specification. Тем не менее, я сильно подозреваю, что это не будет полезно для реализации программного обеспечения, если вы не используете bit-slicing для шифрования многих блоков параллельно.

источник

2013-11-28 12:35:57

Как оптимизировать S-боксы CASUMI?

ответ

Смежные вопросы