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

[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

[gianthare.livejournal.com]

Я не говорю, что это плохая задача. Только на интервью она неуместна, на мой взгляд

[avva.livejournal.com]

несомненно.

[digest.livejournal.com]

На интервью много чего неуместно, но эта задача будет получше вопросов о количестве ремонтников стиральных машин с верхней загрузкой в Новой Зеландии.

[gianthare.livejournal.com]

Не знаю лучше ли, но роднее, конечно ;-)
А кто-нибудь реально попадал на такие задачи на интервью?

[digest.livejournal.com]

Ну есть похожие задачи, конечно. В них действительно интересен ход мыслей кандидата, чем само решение. А мне интересно было мнение хозяина журнала насколько плох показался бы ему кандидат, знающий С, но не предложивший хотя бы примерного направления решения.

[gianthare.livejournal.com]

Я не понимаю, какое там может быть примерное решение - надо сидеть и тупо считать, что куда перейдет.

[avva.livejournal.com]

Мы такие задачи не задаем. Если бы код был "нормальный" - т.е. с статическим массивом из четырех чисел, без трюков с 128, строками и синтаксисом операторов - то я бы ожидал от хорошего кандидата, что он хотя бы предложит направление, в котором думать. Но все равно не спрашивал бы такое; это задача на один трюк, до которого можно не додуматься и все равно быть хорошим программистом.

[digest.livejournal.com]

Отлично, я так почему-то и думал :). Пасиб.

[(Anonymous)]

Итог: несколько десятков хороших программистов думали над этой функцией несколько десятков минут. У каждого в голове примерно терабайт информации и примерно петафлопс вычислительных способностей. Т.о. (с учетом, сколько еще программистов в реальном проекте будут догадываться, что означают вышеуказанные недокументированные magic numbers в коде) вычислительная стоимость функции с точки зрения менеджмента проекта равна по самой скромной оценке примерно одному экзафлопсу. Со знаком "минус".

Не говоря об отсутствии гарантий, что буква 'B' будет следовать в аппаратной таблице символов сразу за буквой 'A' через пять-десять-пятнадцать лет развития компьютеров, или на другой архитектуре.

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