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

[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);

Comments

[avva.livejournal.com]

Э, у компилятора нет проблемы с тем, чтобы выделить память для массива в .data, а не на стеке, и меж тем не считать var указателем. Собственно, и на стек указатели вполне существуют без проблем. Это если определить переменную как register, вот тогда указатель на нее не может существовать.

На уровне ассемблера любой C-массив - указатель. На уровне самого языка имя массива не является указателем (именно для того, чтобы работал sizeof(), в частности), но попытка доступа к нему, т.е. использование имени массива в арифметическом контексте, низвергает его до статуса указателя.

[igogo3000.livejournal.com]

>>> Э, у компилятора нет проблемы с тем, чтобы выделить память для массива в .data, а не на стеке, и меж тем не считать var указателем

Да, так он и детает, если написано static type var[]. А если без static, то, может быть, не делает их соображений типа того, что память под локальные переменные должна быть освобождена по выходу из блока...

>>> Это если определить переменную как register, вот тогда указатель на нее не может существовать

Не спорю :). Но компилятор не создаст автоматически указатель на область памяти, выделенную как например "char s[5];", ибо "char s[5];" означает всего навсего создание объекта размера 5 так же как "int i;" означает создание объекта размера 4.

>>> На уровне ассемблера любой C-массив - указатель

Нет, часто на уровне ассемблера массива вообще не существует. Например, код

void f()
{
  int vars[2];
  vars[0] = 1;
  vars[1] = 2;
  ...
}

после компиляции неотличим от

void f()
{
  int var1;
  int var2;
  var1 = 1;
  var2 = 2;
  ...
}

хотя в первом варианте массив есть, а во втором - нету.

[avva.livejournal.com]

Но компилятор не создаст автоматически указатель на область памяти, выделенную как например "char s[5];", ибо "char s[5];" означает всего навсего создание объекта размера 5 так же как "int i;" означает создание объекта размера 4.

Но если где-то будет выражение s[some_index], то ему придется-таки создавать указатель, не так ли? Независимо от того, на стеке этот массив, или не на стеке. Это, собственно, то, что я хотел сказать: что принципиальной разницы между стеком и секцией данных с точки зрения использования указателей для компилятора не должно быть. Может быть так, что в случае массива, к-й он хочет выделить на стеке, компилятор рассматривает возможность относиться к нему, как к списку переменных, и анализирует для этого код (и скажем, если в коде есть обращения по неизвестным во время компиляции индексам, отказывается от этой оптимизации), а в случае глобального массива он даже не рассматривает такую возможность. Но это уж решение компилятора, модель памяти x86 ему не мешает.

[igogo3000.livejournal.com]

>>> Но если где-то будет выражение s[some_index], то ему придется-таки создавать указатель, не так ли?

Если он и создаст указатель, то это будет не указатель "s", а "s + some_index", но может и не создать никакого. На моем amd64, gcc (без оптимизации) операцию "положить в eax значение s[some_index]" выполняет одной инструкцией, которая является лишь усложненным вариантом инструкции "положить в eax значение локальной переменной x" - т.е. без промежуточных шагов построения указателя (и хранения его в памяти или в регистре).

>>> принципиальной разницы между стеком и секцией данных с точки зрения использования указателей для компилятора не должно быть

Я хотел бы согласиться, но не понял, что Вы в данном контесте называете указателями :). Началось все с того, что главное отличие: стек закеширован, а .data - черте где.

Собственно, что я отстаиваю (не зная, соглашаетесь Вы с этим, или нет): в примере

void f(int i)
{
  const char s2[] = "abc";
  static const char s3[] = "abc"; 
  const char *s4  = "abc";

  char c1 = "abc"[i];
  char c2 = s2[i];
  char c3 = s3[i];
  char c4 = s4[i];
}

Значение c1 будет получено через сдвиг зашитой в бинарник прямо в месте использования константы - адреса глобальной "abc";

c2 - через сдвиг регистра ebp с прибавлением зашитой в бинарник в месте использования константой - расположением s1 в стековом фрейме;

c3 - так же, как c1;

c4 - через сдвиг адреса, прочитанного из стека по адресу расположения s4, равному (чудом) тому, что был зашит в месте получения c1. Вот это и есть настоящий массив и настоящий указатель, а остальное - игрушки. С массивами в куче работают только так.

>>> Может быть так, что в случае массива, к-й он хочет выделить на стеке, компилятор рассматривает возможность относиться к нему, как к списку переменных, и анализирует для этого код

Подозреваю, что это не прихоть компилятора, а требование языка - выделять локальные массивы на стеке. И никакой "оптимизации", от которой компилятор мог бы "отказаться" тут нет - доступ к элементам массива осуществляется через сдвиги на фиксированное или не фиксированное число регистра ebp и взятие значения по полученному адресу (все одной инструкцией).

Хотя все может быть.

[igogo3000.livejournal.com]

опечатка: "расположением s1 в стековом фрейме;" -> "расположением s2 в стековом фрейме;" :)