Шустрый 128-битный LFSR (MMX required)

Случайные числа — темная лошадка обеспечения механизмов безопасности в цифровой среде. Незаслуженно оставаясь в тени криптографических примитивов, они в то же время являются ключевым элементом для генерации сессионных ключей, применяются в численных методах Монте-Карло, в имитационном моделировании и даже для проверки теорий формирования циклонов!

При этом от качества реализации самого генератора псевдослучайных чисел зависит и качество результирующей последовательности. Как говорится: «генерация случайных чисел слишком важна, чтобы оставлять её на волю случая».



Вариантов реализации генератора псевдослучайных чисел достаточно много: Yarrow, использующий традиционные криптопримитивы, такие как AES-256, SHA-1, MD5; интерфейс CryptoAPI от Microsoft; экзотичные Chaos и PRAND и другие.

Но цель этой заметки иная. Здесь я хочу рассмотреть особенность практической реализации одного весьма популярного генератора псевдослучайных чисел, широко используемого к примеру в Unix среде в псевдоустройстве /dev/random, а также в электронике и при создании потоковых шифров. Речь пойдёт об LFSR (Linear Feedback Shift Register).

Дело в том, что есть мнение, будто в случае использования плотных многочленов, состояния регистра LFSR очень медленно просчитываются. Но как мне видится, зачастую проблема не в самом алгоритме (хотя и он конечно не идеал), а в его реализации.

Немного об LFSR


Дословно, LFSR — регистр сдвига с линейной обратной связью, состоящий из двух частей — регистра сдвига и функции обратной связи. Регистр состоит из битов, его длина — количество этих бит.



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



Как не трудно определить, свойства выдаваемой последовательности тесно связаны со свойствами ассоциированного многочлена:

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

Рекомендуемые индексы отводов в зависимости от длины битового поля регистра LFSR хорошо представлены в документе «Efficient Shift Registers, LFSR Counters, and Long PseudoRandom Sequence Generators».

Практическая реализация


Итак, реализация LFSR достаточно проста, но есть мнение, что в силу использования множества битовых операций для просчета плотных многочленов, таких как XOR, скорость работы зачастую оставляет желать лучшего, т.е. ему нужно некоторое время на «разогрев». В качестве альтернативы даже была предложена модификация LFSR со схемой Галуа, цикл из фиксированного числа вызовов функции LFSR в которой выполняется примерно в два раза быстрее.

Честно, не могу с этим согласится. Как я вижу, зачастую проблема не в самом алгоритме, а в его реализации. Обычно мы видим конструкцию следующего типа:

int LFSR (void)
{
  static unsigned long S = 0xFFFFFFFF;
  /* taps: 32 31 30 28 26 1; charact. polynomial: x^32 + x^31 + x^30 + x^28 + x^26 + x^1 + 1 */
  S = ((( (S>>0)^(S>>1)^(S>>2)^(S>>4)^(S>>6)^(S>>31) ) & 1 ) << 31 ) | (S>>1);
  return S & 1;
}


Жестоко. Здесь, как минимум, мы можем избавиться от нескольких XOR и сдвигов, воспользовавшись значением флага четности PF (Parity Flag) регистра флагов. Действительно, сложения по модулю 2 (XOR) определяют четность количества установленных битов. Единственное, флаг четности PF устанавливается, если младший значащий байт результата содержит чётное число единичных (ненулевых) битов, т.е. как минимум один арифметический сдвиг нам сделать все-таки придется:

xor ecx,ecx
mov ebx,0FFFFFFFFh ; S
mov eax,080000057h ; taps (32,31,30,28,26,1)

and ebx,eax
mov cl,ah
sar ebx,018h
lahf
xor cl,ah

sar cl,02h
and cl,01h


В случае, использования плотных многочленов, когда отводы распределены по всему битовому полю 32-х битного регистра, то таких мы получим уже 4 операции сдвига и 3 операции XOR:

xor ecx,ecx
mov ebx,0FFFFFFFFh ; S
mov eax,095324C57h ; taps (32,31,30,28,26,22,21,18,15,12,11,8,6,4,1)

and ebx,eax
lahf
mov cl,ah ; [0-7] bits
sar ebx,08h
lahf
xor cl,ah ; [8-15] bits
sar ebx,08h
lahf
xor cl,ah ; [16-23] bits
sar ebx,08h
lahf
xor cl,ah ; [24-31] bits

sar cl,02h
and cl,01h

Отступление: в случае, когда кол-во сдвигов sar ebx,08h четное либо равно нулю, перед исполнением XOR необходимо инвертировать значение регистра AH, поскольку PF установлен когда кол-во ненулевых битов четное. А нам нужно наоборот.

Что всё же несколько кошернее чем:

int LFSR (void)
{
  static unsigned long S = 0xFFFFFFFF;
  S = ((( (S>>0)^(S>>1)^(S>>2)^(S>>4)^(S>>6)^(S>>10)^(S>>11)^
              (S>>14)^(S>>17)^(S>>20)^(S>>21)^(S>>24)^(S>>26)^
              (S>>28)^(S>>31) ) & 1 ) << 31 ) | (S>>1);
  return S & 1;
}


Следующий шаг — использование регистра для аккумуляции результатов, вместо непосредственного сброса в память на каждом состоянии LFSR:

sal edx,01h
or dl,cl


и так до 32 состояний (edx DWORD), только после чего и записываем в память.

И наконец, в случае, если нам очень необходимо реализовать шустрый 128-битный LFSR (внезапно) мы можем воспользоваться регистрами MMX, что позволит нам на 32-х битном процессоре семейства Pentium реализовать сдвиг без необходимости обращения к памяти (только лишь средствами регистров).

Исходный код
Исходный код на языке ассемблера (x86): pastebin.com/rwKfsYsN
Скомпилированный исполняемый код: www.sendspace.com/file/atg0cf

Update:
Оптимизированная версия кода: pastebin.com/B3kPEaew
Скомпилированный исполняемый код: www.sendspace.com/file/9bl5di

  • 128-bit LFSR
  • используются MMX-регистры
  • архитектура x86
  • смена 2097120 (0FFFFh x 32) состояний регистра LFSR


В итоге


Наконец, о скорости работы — «разогрев» 128-битного LFSR через смену 2 097 120 (0FFFFh x 32) состояний при помощи MMX и регистра флагов с перерывом на кофе (вывод на экран) занял на моем PC порядка 5 секунд. В то же время исполнение программы на C++, написанная по аналогии с вышеприведенной, но для 128-битного варианта и также с выводом на экран, заняло порядка 2-3 минут.

При этом, основной цимес в том, что в варианте использования Parity Flag, плотность многочлена не оказывает сильного влияния на скорость рассчета обратной функции для нового состояния регистра LFSR. А соответственно высказывания в стиле: «Одна из главных проблем РСЛОС состоит в том, что их программная реализация крайне не эффективна. Вам приходиться избегать разреженных многочленов обратной связи так как они приводят к облегчению взлома корреляционным вскрытием. А плотные многочлены очень медленно просчитываются» (отсюда: ru.wikipedia.org/wiki/LFSR ) несколько… несостоятельны и требуют уточнения :)

p.s. И вот что интересно, а можно ли сделать реализацию программы на языке высокого уровня, без ассемлерных вставок, время исполнения которой при переборе 2 097 120 (0FFFFh x 32) состояний для 128-битного LFSR заняло бы… например, менее 0.5 секунды?
Share post

Similar posts

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 40

  • UFO just landed and posted this here
      0
      Отчасти. Конечно, в силу простоты реализации в электронике, LFSR используют в потоковых шифраторах и для скрэмблинга передаваемых данных. Но, скажем так, алгоритм LFSR нашел свое применение не только в электронике, но и в программном коде. Например, при организации пула для энтропии в рамках псевдоустройства /dev/random в версиях Linux.
      +4
      p.s. И вот что интересно, а можно ли сделать


      Думаю что можно. Если вы имели в виду что-то такое:

      #include <inttypes.h>
      #include <stdio.h>
      
      #define TAP_MASK_LOW64 0x0
      #define TAP_MASK_HIGH64 0x28000005
      
      do_lfsr(uint64_t *p)
      {
          uint64_t low  = p[0] & TAP_MASK_LOW64;
          uint64_t high = p[1] & TAP_MASK_HIGH64;
      
          uint64_t s1 = low ^ high;
          uint32_t s2 = (uint32_t)s1 ^ (uint32_t)(s1 >> 32);
          uint32_t s3 = (s2 & 0xffff) ^ (s2 >> 16);
          uint32_t s4 = (s3 & 0xff) ^ (s3 >> 8);
          uint32_t s5 = (s4 & 0xf) ^ (s4 >> 4);
          uint32_t s6 = (s5 & 0x3) ^ (s5 >> 2);
          uint32_t s7 = (s6 & 0x1) ^ (s6 >> 1);
          p[1] = (p[1] << 1) | (p[0] >> 63);
          p[0] = (p[0] << 1) | s7;
      }
      
      int main()
      {
          uint64_t lfsr_data[2] = {
              0xffffffffffffffffull,
              0xffffffffffffffffull,
          };
          volatile unsigned i;
      
          for(i = 0; i < 0xffff * 32; ++i)
              do_lfsr(lfsr_data);
          printf("%016"PRIx64":%016"PRIx64"\n", lfsr_data[1], lfsr_data[0]);
      }
      


      то у меня это выполняется вот столько:

      $ gcc lfsr.c -o lfsr
      $ file lfsr
      lfsr: ELF 32-bit LSB executable, Intel 80386 ...
      $ time ./lfsr
      976a2d15490d6693:844dc6ff26ad7a9a
      
      real    0m0.086s
      user    0m0.084s
      sys     0m0.000s
      


        0
        А оно _точно_ «выполняется», а не печатает статический результат вычисленный в момент компиляции?
          0
          Да. Во-первых это gcc -O0, т.е. никаких оптимизаций, во-вторых, это volatile счётчик цикла, т.е. честный перебор. В третьих даже если внести печать внутрь do_lfsr, то картинка такая:
          .......
          1b976a2d15490d66:93844dc6ff26ad7a
          372ed45a2a921acd:27089b8dfe4d5af5
          6e5da8b45524359a:4e11371bfc9ab5ea
          dcbb5168aa486b34:9c226e37f9356bd4
          b976a2d15490d669:3844dc6ff26ad7a9
          72ed45a2a921acd2:7089b8dfe4d5af53
          e5da8b45524359a4:e11371bfc9ab5ea6
          cbb5168aa486b349:c226e37f9356bd4d
          976a2d15490d6693:844dc6ff26ad7a9a
          976a2d15490d6693:844dc6ff26ad7a9a
          
          real    0m33.816s
          user    0m1.560s
          sys     0m6.288s
          
            +1
            ну я -O0 не заметил :)
          0
          datacompboy@nuuzerpogodible:~$ time ./lfsr 0
          976a2d15490d6693:844dc6ff26ad7a9a

          real 0m0.019s
          user 0m0.016s
          sys 0m0.004s

          Точно выполняется…
          int main(int argc, char ** argv)
          {
              uint64_t lfsr_data[2] = {
                  0xffffffffffffffffull,
                  0xffffffffffffffffull,
              };
              volatile unsigned i;
          
              if(argc < 2) {
                  printf("Run as \"%s 0\"\n", argv[0]);
                  return 1;
              }
          
              uint64_t arg;
              sscanf(argv[1], "%llu", &arg);
              lfsr_data[0] += arg;
              lfsr_data[1] += arg;
              for(i = 0; i < 0xffff * 32; ++i)
                  do_lfsr(lfsr_data);
              printf("%016"PRIx64":%016"PRIx64"\n", lfsr_data[1], lfsr_data[0]);
          }
          
          –2
          Хах :) Действительно, забыл добавить условие вывода на экран всех вычисленных функцией обратной связи битов.
            +3
            Так мы скорость вывода будем замерять, а не сдвиговый регистр.
            Потому что с полным выводом в консоль я вижу 33 секунды, в файл — 1.2 секунды, а в /dev/null — 0.95
              0
              Отлично… Ну что же, мой результат ~0.04 с
              0
              Хорошо, «будь по-твоему, старче»:

              #include <inttypes.h>
              #include <stdio.h>
              
              #define TAP_MASK_LOW64 0x0
              #define TAP_MASK_HIGH64 0x28000005
              
              void do_lfsr(uint64_t *p)
              {
                  uint64_t low  = p[0] & TAP_MASK_LOW64;
                  uint64_t high = p[1] & TAP_MASK_HIGH64;
              
                  uint64_t s1 = low ^ high;
                  uint32_t s2 = (uint32_t)s1 ^ (uint32_t)(s1 >> 32);
                  uint32_t s3 = (s2 & 0xffff) ^ (s2 >> 16);
                  uint32_t s4 = (s3 & 0xff) ^ (s3 >> 8);
                  uint32_t s5 = (s4 & 0xf) ^ (s4 >> 4);
                  uint32_t s6 = (s5 & 0x3) ^ (s5 >> 2);
                  uint32_t s7 = (s6 & 0x1) ^ (s6 >> 1);
                  p[1] = (p[1] << 1) | (p[0] >> 63);
                  p[0] = (p[0] << 1) | s7;
                  putchar(s7 ? '1' : '0');
              }
              
              int main()
              {
                  uint64_t lfsr_data[2] = {
                      0xffffffffffffffffull,
                      0xffffffffffffffffull,
                  };
                  volatile unsigned i;
              
                  for(i = 0; i < 0xffff * 32; ++i)
                      do_lfsr(lfsr_data);
                  printf("\n%016"PRIx64":%016"PRIx64"\n", lfsr_data[1], lfsr_data[0]);
                  return 0;
              }
              


              ......
              111011011111100001110100101111001110011100001110001111011000001100110100001111101100010101010100100001110000000001000000010011000001000001000011100101000011111101000000011101110110100000110101111001100010110010111101011010010000110100000010010010100001010101001001011110001110101010010000010111010101100001001111011111001110100110111110111000010001101110010111011010100010110100010101010010010000110101100110100100111000010001001101110001101111111100100110101011010111101010011010
              976a2d15490d6693:844dc6ff26ad7a9a
              
              real    0m0.577s
              user    0m0.104s
              sys     0m0.028s
              

                0
                А если занести четность 16-битных чисел в массив — не будет быстрее?
                s7=Parity[s3];
                  +1
                  Я думаю, что с высокой вероятностью не будет, из-за кэша, но не проверял.
                  С другой стороны, 4- или 8-битная табличка почти наверняка даст ускорение.
                    0
                    Уже проверил. Для массивов время на 2^21 циклов — 0.0354, для чистого xor — 0.0445 (VS2008, 32-битный режим).
                      0
                      И, кстати, на 32-битных числах получается 0.0192 сек:

                      unsigned int AR[4];
                      void step3(){
                      	unsigned int q=(AR[0]&Mask0)^(AR[1]&Mask1)^(AR[2]&Mask2)^(AR[3]&Mask3);
                      	unsigned int c=u[(q&0xffff)^(q>>16)];
                      	AR[3]=(AR[3]<<1)|(AR[2]>>31);
                      	AR[2]=(AR[2]<<1)|(AR[1]>>31);
                      	AR[1]=(AR[1]<<1)|(AR[0]>>31);
                      	AR[0]=(AR[0]<<1)|c;
                      	*r1++=c;
                      }
                      


                      Но я еще не смотрел, что там получилось в ассемблере.
                        0
                        А если реализовать через локальные переменные:

                        void step3(int m){
                        	unsigned int a=AR[0],b=AR[1],c=AR[2],d=AR[3];
                        	do{
                        		unsigned int q=(a&Mask0)^(b&Mask1)^(c&Mask2)^(d&Mask3);
                        		q=u[(q&0xffff)^(q>>16)];
                        		d=(d<<1)|(c>>31);
                        		c=(d<<1)|(b>>31);
                        		b=(d<<1)|(a>>31);
                        		a=(d<<1)|(q);
                        		*r1++=q;
                        	}while(--m);
                        	AR[0]=a; AR[1]=b; AR[2]=c; AR[3]=d;
                        }
                        

                        то получается 0.00849 сек на 2^21 циклов.
                        Для 2^28 циклов 64-битный xor дает 5.630с, с 16-битной табличкой — 4.546с, 32-битный на локальных переменных — 1.072с.
                        0
                        Мои цифры (2 ^ 28 циклов): только xor — 1.889с, 4-битная таблица — 1.677с, 8-битная — 1.517с
                +1
                только хардкор, только непереносимый код! ;)

                почему именно MMX, а не SSE/SSE2?
                  +3
                  Чтобы огрести проблем с FPU, не? (:
                  А если серьёзно, скажите, какой смысл использовать в этой задаче любую из названных технологий?
                  Если говорить о расширенных наборах инструкций, я вижу (и то сомнительный) выигрыш только от использования popcnt.
                    –1
                    в XXI веке живем, считаю, что оптимизацией должен заниматься копилятор :)
                      +1
                      Согласен :) Более того, если я правильно помню, то на тот момент, когда мне необходим был этот код, технология SSE2 была очень молода, а команды SSE мне показались не очень «удобными».
                        0
                        xorps, andps выглядят как перспективные для данной задачи
                          0
                          Ну а мне они таковыми не кажутся, потому что узкое место не там.
                          Если интересно — предложите код, обсудим.
                      +1
                      Весело у вас. Я давно с ассемблером не экспериментировал, а тут решил попробовать. Когда замена одного регистра в арифметической команде увеличивает время работы на 16 тактов — это круто!
                        +1
                        Быстрее всего получилось с 8-битной таблицей. Главный цикл выглядит так:

                        	mov	DWORD PTR _m$[esp+20], 65536
                        	npad	5
                        $LL3@step3:
                        	push	ebx
                        	mov	ebx,1
                        	npad	10
                        $LL4@step3:	
                        	mov	eax, edi
                        	and	eax, MASK3
                        	mov	ebp, ecx
                        	and	ebp, MASK2
                        	xor	eax, ebp
                        	mov	ebp, edx
                        	and	ebp, MASK1
                        	xor	eax, ebp
                        	mov	ebp, esi
                        	and	ebp, MASK0
                        	xor	eax, ebp
                        
                        	mov	ebp, eax
                        	shr	ebp, 16	
                        	xor	ebp, eax
                        	mov	eax, ebp
                        	shr	ebp, 8	
                        	xor	ebp, eax
                        	and	ebp, 255
                        	movzx	eax, BYTE PTR _u[ebp]
                        
                        	shld	edi,ecx,1
                        	shld	ecx,edx,1
                        	shld	edx,esi,1
                        	add	esi,esi
                        	or	esi,eax
                        	ror	eax,1
                        	rcl	ebx,1
                        
                        	jnc	short $LL4@step3
                        	mov	eax,ebx
                        	pop	ebx
                        	mov	DWORD PTR [ebx], eax
                        	add	ebx,4
                        
                        	sub	DWORD PTR _m$[esp+20], 1	
                        	jne	$LL3@step3
                        
                        

                        (программа переделана из листинга C++, поэтому метки странные).

                        На 2^28 циклов дает 1.46 секунды (предыдущая «быстрая» программа была с ошибкой, даже с тремя).
                          0
                          Вы об ошибках с «d<<1»? :)

                          Судя по сгенерированному коду, полином задается через константы. Мне кажется исполняемый код не даст такие же результаты, если полином будет меняться в процессе работы, например циклический сдвиг. Фактически, вся логика работы с 256 битами данных (регистр и маска), была сокращена до 128 и аккуратно разбросана по стандартным регистрам.

                          Я немного оптимизировал код. Он стал похож на Ваш и jcmvbkbc вариант, только вместо таблиц у меня lahf/not:

                            mov ecx, RR_
                          l1:
                            ; Apply LFSR mask
                            movq mm(inRTmpH),mm(inRSH)
                            pand mm(inRTmpH),mm(inRMH)
                            movq mm(inRTmpL),mm(inRSL)
                            pand mm(inRTmpL),mm(inRML)
                          
                            ; Calculate new bit
                            pxor mm(inRTmpH),mm(inRTmpL)
                            movd ebx, mm(inRTmpH)
                            psrlq mm(inRTmpH),020h
                            movd eax, mm(inRTmpH)
                            xor ebx,eax
                            mov ax,bx
                            sar ebx,010h
                            xor ax,bx
                            xor al,ah
                            lahf
                            not eax
                            sar eax,0Ah
                            and eax,01h
                          
                          ; Append new bit
                            psrlq mm(inRSL),01h
                            movq mm(inRTmp),mm(inRSH)
                            psllq mm(inRTmp),03Fh
                            por mm(inRSL),mm(inRTmp)
                            psrlq mm(inRSH),01h
                            movd mm(inRTmp), eax
                            psllq mm(inRTmp),03Fh
                            por mm(inRSH),mm(inRTmp)
                          
                            loop l1
                          


                          На 2^21 циклах скорость работы ~0.02 с. Но, зато, я легко могу добавить конструкцию следующего типа без обращения к памяти:

                            movq mm(inRTmpH),mm(inRSH)
                            movq mm(inRTmpL),mm(inRSH)
                            psllq mm(inRTmpH),03Fh
                            psllq mm(inRTmpL),03Fh
                            psrlq mm(inRSH),01h  
                            psrlq mm(inRSL),01h  
                            por mm(inRSH),mm(inRTmpL)
                            por mm(inRSL),mm(inRTmpH)
                          


                          Жаль что в MMX нет SHLD :)
                            0
                              movq mm(inRTmpH),mm(inRMH)
                              movq mm(inRTmpL),mm(inRML)
                              psllq mm(inRTmpH),03Fh
                              psllq mm(inRTmpL),03Fh
                              psrlq mm(inRMH),01h  
                              psrlq mm(inRML),01h  
                              por mm(inRMH),mm(inRTmpL)
                              por mm(inRML),mm(inRTmpH)


                            конечно же…
                              0
                              Можно и без SHLD:
                              	add	esi,esi
                              	adc	edx,edx
                              	adc	ecx,ecx
                              	adc	edi,edi
                              	or	esi,eax
                              

                              При 8-битной таблице так получилось даже быстрее, чем с shld — 1.17 сек на 2^28 циклов. Пока таблица была 16-битной, adc работал медленнее.
                                0
                                Да, это бесспорно. Но опять же, маска остается константой. Да и в инструкциях MMX нет аналога ADC, к сожалению.
                                  0
                                  А вообще бит C там есть? Вместо adc, например в 8086, можно обойтись и rcl. Но вообще без C писать длинную арифметику непросто (если нет команд сложения с переполнением).
                                    0
                                    Там команд то… на пальцах задней ноги пересчитать можно. Что по поводу флагов, то:

                                    «The packed arithmetic instructions operate on a set of bytes, words, or double words within a 64-bit block. For example, the PADDW instruction computes four 16-bit sums of two operand simultaneously. None of these instructions affect the CPU's FLAGs register. Therefore, there is no indication of overflow, underflow, zero result, negative result, etc.»

                                    Отсюда: Art of Assembly: MMX Technology Instructions

                                    Жаль, что не ввели сразу «горизонтальную» арифметку. Сильно упростило бы.
                              0
                              И, кстати, взятие маски из памяти:

                              and eax, DWORD PTR _AM+12

                              и т.п. вообще не повлияло на скорость — осталось 1.17 сек
                                0
                                А Вы уверены, что на выходе компилера, эта инструкция не превращается что-то типа в следующий opcode? :)

                                25 78563412
                                  0
                                  В листинге написано

                                  00000042 23 05 0000000C E and eax, DWORD PTR _AM+12

                                  Так что не превращается. Да и с чего бы? Массив с маской описан в соседнем файле.
                                    0
                                    Андрей, а можете поделиться уже скомпилированным кодом?
                                      0
                                      astr73.narod.ru/Files/cpol.zip — там cpp и asm (исходники), lst, полученный из asm и собранный exe (32-битное консольное приложение для Windows)
                                        0
                                        Спасибо… Кажется, я был прав (смещение в EXE-файле: 0x05B5):

                                        002811B5  |. 8BDA                            ||MOV EBX,EDX
                                        002811B7  |. 81E3 563412F0                   ||AND EBX,F0123456
                                        002811BD  |. 8BC8                            ||MOV ECX,EAX
                                        002811BF  |. 81E1 F0DEBC9A                   ||AND ECX,9ABCDEF0
                                        002811C5  |. 33D9                            ||XOR EBX,ECX
                                        
                                          0
                                          Да, это похоже на фрагмент откомпилированной C-шной функции step1 (оставленной для контроля). Правда, регистры я сейчас вижу совсем другие:

                                          003E103A  mov         ebx,dword ptr [esp+24h] 
                                          003E103E  and         ebx,12345679h 
                                          003E1044  mov         edi,ebp 
                                          003E1046  mov         ecx,esi 
                                          003E1048  and         ecx,0F0123456h 
                                          003E104E  mov         eax,edx 
                                          003E1050  and         eax,789ABCDEh 
                                          003E1055  xor         eax,ebx 
                                          003E1057  and         edi,9ABCDEF0h 
                                          003E105D  xor         ecx,edi 
                                          
                                            +1
                                            Да, так и есть. Запутали меня (:

                                            013E1400   > 8BC7           MOV EAX,EDI
                                            013E1402   . 2305 44303E01  AND EAX,DWORD PTR DS:[13E3044]
                                            013E1408   . 8BE9           MOV EBP,ECX
                                            013E140A   . 232D 40303E01  AND EBP,DWORD PTR DS:[13E3040]
                                            013E1410   . 33C5           XOR EAX,EBP
                                            013E1412   . 8BEA           MOV EBP,EDX
                                            013E1414   . 232D 3C303E01  AND EBP,DWORD PTR DS:[13E303C]
                                            013E141A   . 33C5           XOR EAX,EBP
                                            013E141C   . 8BEE           MOV EBP,ESI
                                            013E141E   . 232D 38303E01  AND EBP,DWORD PTR DS:[13E3038]
                                            

                                            Похоже, использование таблиц в данном случае эффективнее.

                                            Кстати, вот тоже работающий вариант не использующий XOR в принципе (:
                                            (правда медленный):

                                            .data
                                              SH_ dq 0FFFFFFFFFFFFFFFFh ; Sequence[127-64]
                                              SL_ dq 0FFFFFFFFFFFFFFFFh ;         [63-0]
                                              MH_ dq 00000000000000000h ; Mask[127-64] taps: 128,126,101,99
                                              ML_ dq 00000000028000005h ;     [63-0]
                                              RR_ dd 0001FFFE0h         ; Amount of rounds
                                            
                                              _55 dq 05555555555555555h
                                              _33 dq 03333333333333333h
                                              _0F dq 00F0F0F0F0F0F0F0Fh
                                              _FF dq 000FF00FF00FF00FFh
                                            
                                            .code
                                              ; Initialize MMX registers
                                              movq mm(inRSH),SH_
                                              movq mm(inRSL),SL_
                                              movq mm(inRMH),MH_
                                              movq mm(inRML),ML_
                                            
                                              mov ecx, RR_
                                            l1:
                                              ; Apply LFSR mask
                                              movq mm(inRTmpH),mm(inRSH)
                                              pand mm(inRTmpH),mm(inRMH)
                                              movq mm(inRTmpL),mm(inRSL)
                                              pand mm(inRTmpL),mm(inRML)
                                            
                                              ; Calculate new bit
                                              movq mm(inRTmp),mm(inRTmpH)
                                              movq mm(inRTmpH),mm(inRTmpL)
                                              psrlw mm(inRTmpH),01h
                                              pand mm(inRTmpH),_55
                                              pand mm(inRTmpL),_55
                                              paddw mm(inRTmpL),mm(inRTmpH)
                                              movq mm(inRTmpH),mm(inRTmpL)
                                              psrlw mm(inRTmpH),02h
                                              pand mm(inRTmpH),_33
                                              pand mm(inRTmpL),_33
                                              paddw mm(inRTmpL),mm(inRTmpH)
                                              movq mm(inRTmpH),mm(inRTmpL)
                                              psrlw mm(inRTmpH),04h
                                              pand mm(inRTmpH),_0F
                                              pand mm(inRTmpL),_0F
                                              paddw mm(inRTmpL),mm(inRTmpH)
                                              movq mm(inRTmpH),mm(inRTmpL)
                                              psrlw mm(inRTmpH),08h
                                              pand mm(inRTmpH),_FF
                                              pand mm(inRTmpL),_FF
                                              paddw mm(inRTmpL),mm(inRTmpH)
                                              movq mm(inRTmpH),mm(inRTmpL)
                                              psllq mm(inRTmpL),020h
                                              paddd mm(inRTmpH),mm(inRTmpL)
                                              movq mm(inRTmpL),mm(inRTmpH)
                                              psllq mm(inRTmpL),010h
                                              paddw mm(inRTmpH),mm(inRTmpL)
                                              psllq mm(inRTmpH),0Fh
                                              movq mm(inRTmpL),mm(inRTmp)
                                              movq mm(inRTmp),mm(inRTmpH)
                                              movq mm(inRTmpH),mm(inRTmpL)
                                              psrlw mm(inRTmpH),01h
                                              pand mm(inRTmpH),_55
                                              pand mm(inRTmpL),_55
                                              paddw mm(inRTmpL),mm(inRTmpH)
                                              movq mm(inRTmpH),mm(inRTmpL)
                                              psrlw mm(inRTmpH),02h
                                              pand mm(inRTmpH),_33
                                              pand mm(inRTmpL),_33
                                              paddw mm(inRTmpL),mm(inRTmpH)
                                              movq mm(inRTmpH),mm(inRTmpL)
                                              psrlw mm(inRTmpH),04h
                                              pand mm(inRTmpH),_0F
                                              pand mm(inRTmpL),_0F
                                              paddw mm(inRTmpL),mm(inRTmpH)
                                              movq mm(inRTmpH),mm(inRTmpL)
                                              psrlw mm(inRTmpH),08h
                                              pand mm(inRTmpH),_FF
                                              pand mm(inRTmpL),_FF
                                              paddw mm(inRTmpL),mm(inRTmpH)
                                              movq mm(inRTmpH),mm(inRTmpL)
                                              psllq mm(inRTmpL),020h
                                              paddd mm(inRTmpH),mm(inRTmpL)
                                              movq mm(inRTmpL),mm(inRTmpH)
                                              psllq mm(inRTmpL),010h
                                              paddw mm(inRTmpH),mm(inRTmpL)
                                              psllq mm(inRTmpH),0Fh
                                              paddw mm(inRTmpH),mm(inRTmp)
                                              psrlq mm(inRTmpH),03Fh
                                              psllq mm(inRTmpH),03Fh
                                            
                                              ; Append new bit
                                              psrlq mm(inRSL),01h
                                              movq mm(inRTmp),mm(inRSH)
                                              psllq mm(inRTmp),03Fh
                                              por mm(inRSL),mm(inRTmp)
                                              psrlq mm(inRSH),01h
                                              por mm(inRSH),mm(inRTmpH)
                                            

                          Only users with full accounts can post comments. Log in, please.