avva | небольшая разгадка для программистов

Итак, подробное обсуждение вчерашней загадки: что именно делает функция

unsigned char func(unsigned char c) {
  return c - 128 + (c >> 5&3)["(PI)"];
}

и как она это делает?

Правильный ответ: эта функция переводит шестнадцатиричную цифру в ее значение, причем как большие буквы, так и маленькие. Иными словами, эта функция переводит '0'...'9' в 0..9, 'A'...'F' в 10...15, и 'a'...'f' в 10...15. Подходящее название для этой функции - hex2int (или hex_to_int, или HexToInt, как пожелаете).

Первым правильный ответ дал

renatm, второй -

ashalynd. Потом еще многие дали правильный ответ. Некоторые комментаторы справедливо заметили, что функция работает не только для 16-ричных цифр, но и для других оснований, до конца алфавита. Это верно, но скорее побочный эффект, а не задумано так: в оригинале функция назывались HexToInt.

Немного о том, как это происходит. Запись "c >> 5&3" специально обманчива, потому что очередность операторов такова, что на самом деле это (c >> 5) & 3. Т.е. вынимаем из c шестой и седьмой биты. Далее, странное применение оператора [] - это старый трюк, который иногда используется для специального усложнения исходников, и больше ни на что особенно не годен. Дело в том, что в стандартах C и C++ значение оператора [] определяется так: a[b] это ровно то же самое, что *(a+b). Это формальное выражение известного принципа о том, что работа с массивами в C сводится (по большей части) к арифметике с указателями. А это значит, что, например, a[1] и 1[a] - совершенно одно и то же, хотя второй вариант выглядит странно и в нормальных программах никто так никогда не пишет.

Так что эта часть функции сводится к "(PI)"[(c>>5) &3]. Это значит, что из c мы вычитаем 128, а потом прибавляем, в зависимости от 6-7 бит c, одно из чисел 40, 80, 73, 41 (численные значения '(', 'P', 'I', ')' ).
Поскольку вся арифметика тут 8-битная беззнаковая (unsigned), то тот факт, что при вычитании 128 мы можем перепрыгнуть в верхние 128 байт, а потом при прибавлении перепрыгнуть 0 обратно, никакой роли не играет, и можно это упростить так: -128 + 40/80/73/41 все равно, что -88/-48/-55/-87, в зависимости от шестого-седьмого бита c. Ну а теперь осталось заметить, что это можно написать так: -88 / -'0' / -('A'-10) / -('a'-10), а также заметить, что для символов '0'..'9', 'A'..'F', 'a'..f' шестой и седьмой биты получаются соответственно 1, 2 и 3. Теперь, надеюсь, понятно, почему получается желаемый результат. Первое число из четырех - оно же левая скобка '(' - вообще никакой роли не играет, и я выбрал ее просто для симметрии, чтобы получилась красивая строка (PI).

До того, как над ней поработали усложнители (до меня - еще несколько коллег на внутренней рассылке), исходная функция выглядела так:

inline unsigned char HexToInt(unsigned char c) {	 
  DCHECK(IsHexDigit(c));	 
  static unsigned char kOffset[4] = {0, 0x30u, 0x37u, 0x57u};	 
  return c - kOffset[(c >> 5) & 3];	 
}

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

Наверное, кому-то может быть интересно знать, зачем вообще писать эту функцию таким странным и непонятным способом, а не очевидный код, который проверяет, находится ли символ между '0' и '9', и тогда вычитает '0', потом между 'A' и 'F', и так далее. Все это можно написать одним выражением, используя оператор ?:, конечно. Этот вопрос затрагивает интересные и весьма нетривиальные соображения насчет оптимизации кода для современных CPU. С одной стороны, чем меньше код обращается к памяти, тем лучше, потому что обращение к памяти, особенно не попадающее в кэш процессора, занимает в наше время астрономическое время по сравнению с операциями в регистрах - в десятки или сотни раз дольше. Да и даже если обращение попадает в кэш, это может означать, что что-нибудь другое полезное туда не попадет, он ведь не резиновый. Поэтому, казалось бы, эта версия с массивом должна быть медленней, чем "очевидный" код, который я описал выше. Но с другой стороны, в "очевидной" версии есть условные переходы (после сравнения мы выбираем, что дальше делать), а они на современных архитектурах тоже весьма дороги, потому что если процессору не удастся верно угадать, какой из двух выборов ему предстоит совершить, то ему придется обнулить конвейер (flush the pipeline) уже прочитанных и приготовленных инструкций.

Поэтому я не знаю точно, какая из двух версий функции HexToInt - "очевидная", сравнивающая символы, или "странная", приведенная выше, быстрее на практике. Подозреваю, что зависит от того, как часто она вызывается: если миллионы раз подряд, то наверняка быстрее "странная", потому что вспомогательный массив будет плотно сидеть в кэше все время; если редко, то "очевидная" может оказаться быстрее. В любом случае, если нет необходимости оптимизировать именно эту функцию - а такую функцию почти никогда нет нужды оптимизировать - я лично написал бы "очевидную" версию, конечно - именно потому, что ее легче прочесть и сразу понять.

В качестве подарка тем, кто дочитал до конца - еще две версии функции HexToInt; подозреваю, что они обе быстрее тех двух, что я рассматривал выше. Несомненно, вы сами теперь сможете разобраться, как они работают.

Первая версия взята из исходников SQLite:

return (c + 9*(1 & (c>>6))) & 15;

Вторую версию написал на рабочей рассылке коллега по имени Дэвид Тернер:

return c - (0x57373000 >> (c >> 5)*8);

Flat | Top-Level Comments Only

From:

migmit.livejournal.com

Помнится, в замечательной игрушке "Heroes of MatMex" один из монс...преподавателей предлагал игроку написать визуализацию байта за 11 байт.

Я пока так и не знаю, как это делается.

From:

imenno.livejournal.com

По-видимому, надо это сделать на каком-то ассемблере? Каком?

From:

migmit.livejournal.com

Ну, кроме x86 мы тогда вообще ничего не знали.
Мозговой штурм предложил следующую формализацию задачи: 16-битный x86, исходно в некотором (по желанию программиста) 8-битном регистре находится нужный байт, содержимое прочих регистров неизвестно; на выходе в 16-битном регистре (тоже по выбору программиста) находятся ASCII-коды двух 16-ричных цифр, составляющих этот байт, в любом удобном регистре.
В общем, задачу мы всё равно не решили. Лучшим приближением стал найденный в какой-то книжке способ визуализации половинки байта за 5 байт.

(...)

небольшая разгадка для программистов

Page Summary

Style Credit

Expand Cut Tags