Говнокод по пятницам. Эпизод 2. Перверсивное реверсирование

Программирование Уроки программирования @ЕвгенийП
1

Ну, что опять пятница и опять неудержимо хочется поговнокодить.

Вспомнился тут конкурс, который объявляли ребята из летней школы программирования на самый изращенческий (если желаете «по-умному», то «самый перверсивный») способ реверсирование байта. Т.е. задача реверсировать байт, чтобы 0-ой бит оказался на 7-ой позиции, 1-ый – на 6-ой и т.д. и сделать это надо было наиболее извращённым способом.

Ну, сказала Сова, обычная процедура в таких случаях нижеследующая самая что ни на есть обычная программа реверсирования байта (которую использует чуть менее, чем все) выглядит примерно так:

uint8_t bitReverseFast(uint8_t b) {
   b = (b & 0xF0) >> 4 | (b & 0x0F) << 4; // меняем местами нибблы (4-ки битов)
   b = (b & 0xCC) >> 2 | (b & 0x33) << 2; // внутри каждой четвёрки меняем местами пары битов
   return (b & 0xAA) >> 1 | (b & 0x55) << 1;	// внутри каждой пары меняем местами биты
}

как видите, ничего особо умного и сложного нет и такими приземлённо-рутинными вещами армянское радио, разумеется, не занимается.

Задача стояла сделать тоже самое но … «через Альпы». Мы почему-то были уверены, что победит русский студент – у нас ведь всё «через Альпы» делается, так что нашим ребятам не привыкать. Но, к нашему удивлению, победил китайский участник (видимо, с «Альпами» у них в Поднебесной тоже всё в порядке).

Решение было вот таким:

uint8_t bitReversePervert(const uint8_t b) {
	return (b * 0x0202020202ull & 0x010884422010ull) % 1023; // сами разбирайтесь :-)
}

Можете запустить и убедиться, что оба решения вполне исправно реверсируют биты.

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

Ну, вот такой вот говнокодик. Если вставить эту функцию в проект, да ещё и без комментариев (а лучше и название оставить типа f()), то выглядеть она будет вполне достойно :slight_smile:

Кто-то может предложить более гнусное извращение на эту тему?

3 лайка
2 
uint8_t reverse_moderate(uint8_t b) {
  uint8_t a =0; uint8_t c = 8;
  while (c--) {
    a>>=1;  a |= (b & 0x80 );  b<<=1;
    }
return a;
}

Добавка: Медленнее “стандартного решения”, приведенного @ЕвгенийП - на 20%, при этом компактнее примерно вдвое.

Добавка2: Зато если перейти к реверсированию uint16 или тем паче 32 - “стандартное решение” сдохнет… а этому пофиг.

4

Спасибо

5

Нет, почему? Просто ещё строчку дописать надо, т.к. будет не три этапа, как сейчас, а 4 (для 16 бит) или 5 для 32. и вообще, таких этапов будет “логарифм размерности по основанию 2”.

6

ну не решение “сдохнет”, а программист от сложности кода :slight_smile: Что-то мне представилось, что для 32бит там будет строчек 10-12 “обменов” байтами

что типа такого:


uint32_t reverse_integer_bits(uint32_t b) {
   uint32_t mask = 0b11111111111111110000000000000000;
   b = (b & mask) >> 16 | (b & ~mask) << 16;
   mask = 0b11111111000000001111111100000000;
   b = (b & mask) >> 8 | (b & ~mask) << 8;
   mask = 0b11110000111100001111000011110000;
   b = (b & mask) >> 4 | (b & ~mask) << 4;
   mask = 0b11001100110011001100110011001100;
   b = (b & mask) >> 2 | (b & ~mask) << 2;
   mask = 0b10101010101010101010101010101010;
   b = (b & mask) >> 1 | (b & ~mask) << 1;
   return b;
}
7

Ну лично я взял бы два стека.
Сначала побитово запихнул число в первый стек.
Затем также побитово перенес число из первого стека во второй.
И, наконец, из второго стека побитово извлек число туда, куда надо.
На 32-разрядном камне только под тела стеков нужно 256 байтов.

8

самое главное абсолютно всё прозрачно, ни одной извилины напрягать не надо, ошибиться практически невозможно

9

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

10

Во-во. А тут одна строчка c красивыми константами :stuck_out_tongue_winking_eye:

11

Разве это “гнусное извращение”?
Гнусное извращение должно просто сбивать с ног своей фундаментальностью.

12

В ассемблерах есть сдвиг через флаг (rol ror для avr) и есть обмен полубайтами (swap для avr)… в некоторых камнях есть и реверсирование 32 бит за одну команду …

13

я знаю самый быстрый метод для байта, за один так процессора ))) (для Интел)

14

Ну, кто ж виноват, что Вы такой устойчивый? :slight_smile: Меня впечатлило реально, даже несмотря на то, что я раньше это решение где-то в литературе видел.

15

Вот, когда будем говорить про интел, тогда и обсудим.

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

16

Кто-то хочет понять математику китайского решения? Просто так распинаться не буду, тем более в чужой ветке, но если кому-то интересно, то могу объяснить и заодно станет понятно, как такое обобщать и строить.

17

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

Спойлер 
uint8_t bitRvrss_ (uint8_t inbyte)
{
  uint16_t i = 256;
  uint8_t outbyte = 0;

  while ((i /= 2) > 0)
  {
    if (inbyte % 2)
      outbyte += (uint8_t)i;
    inbyte /= 2;
  }
  return outbyte;
}

Ещё

Спойлер 

uint8_t bitRvrs (uint8_t inbyte)
{
  uint8_t outbyte;
  uint8_t i = 0;
  uint8_t b = 7;
  while (i < 8)
  {
    bitWrite(outbyte, b, bitRead(inbyte, i));
    i++;
    b--;
  }
  return outbyte;
}
1 лайк
18

Говнокодить тоже нужно уметь. Приходилось заниматься бэкдорами. Утомительно всё это и не по душе. Тут хоть бы в своём коде разобраться через некоторое время, не то что… Плюс дополнительные баги и, как следствие, дополнительно возникающие хлопоты.

19

На скорость будет 17 тактов и 36 байт…

uint8_t __attribute__((noinline)) rb(uint8_t b) {
  uint8_t r;
  asm volatile (
    "ROL %1 \n\t"
    "ROR %0 \n\t"
    "ROL %1 \n\t"
    "ROR %0 \n\t"
    "ROL %1 \n\t"
    "ROR %0 \n\t"
    "ROL %1 \n\t"
    "ROR %0 \n\t"
    "ROL %1 \n\t"
    "ROR %0 \n\t"
    "ROL %1 \n\t"
    "ROR %0 \n\t"
    "ROL %1 \n\t"
    "ROR %0 \n\t"
    "ROL %1 \n\t"
    "ROR %0 \n\t"
    : "=&r" (r)
    : "r" (b)
    :);
  return r;
}

void setup () {
  Serial.begin(9600);
  Serial.println("Start");
}

void loop() {
  Serial.println(0B11000001, BIN);
  Serial.println(rb(0B11000001), BIN);
}

Вместе с вызовом и возвратом 25 тактов …

MOV  R25,R24
ROL R25
ROR R24
ROL R25
ROR R24
ROL R25
ROR R24
ROL R25
ROR R24
ROL R25
ROR R24
ROL R25
ROR R24
ROL R25
ROR R24
ROL R25
ROR R24
RET

Если упереться в размер кода, то 14 байт:

uint8_t __attribute__((noinline)) rb(uint8_t b) {
  uint8_t r;
  uint8_t c(8);
  asm volatile (
    "loop1: \n\t"
    "ROL %1 \n\t"
    "ROR %0 \n\t"
    "DEC %2 \n\t"
    "BRNE loop1 \n\t"
    : "=&r" (r)
    : "r" (b), "r"(c)
    :);
  return r;
}

Вместе с вызовом и возвратом уже будет 49 тактов …

20

Ну, мне с этим попроще будет, иногда и не хочешь, а само как-то получается))

1 лайк
21

Ну, само это не то. Это примерно, как абстрактная живопись. Само может получиться – опрокинуть банку с краской. А вот “говнокод как искусство” – такое само не получается.