ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Ассемблер - регистры MMX - команды условного перехода.
25 сообщений из 225, страница 8 из 9
  8  все
Ассемблер - регистры MMX - команды условного перехода.
    #39658884
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Barlone,

clang понравился:
-без фрейма,
-догадался насчет декремента,
-заменил работу с маской -1 на условную пересылку,
-все сравнения or-ами.
...
Рейтинг: 0 / 0
09.06.2018, 14:14
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658888
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®...И 33-й - это только начало и почва для отладки...

Т.е. процедура должна работать и на 34 бита?
...
Рейтинг: 0 / 0
09.06.2018, 14:17
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658916
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
AR®,

как то жёстко 21481207 , на i7 42 секунды по сравнению с 14.8 на плюсах
...
Рейтинг: 0 / 0
09.06.2018, 14:43
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658934
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Aleksandr SharahovТ.е. процедура должна работать и на 34 бита?
И на 34, и на 35..64.
32-битная версия удовлетворительно работала на C#. Переход к 64-битной арифметике вынудил вспомнить про C и написание dll.
...
Рейтинг: 0 / 0
09.06.2018, 14:58
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39658936
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
kealon(Ruslan)AR®, как то жёстко 21481207 , на i7 42 секунды по сравнению с 14.8 на плюсах

Закомментируйте часть с метки test_d: до метки test_c:, на Вашем i7 будет секунд 10-12.
...
Рейтинг: 0 / 0
09.06.2018, 15:00
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659057
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
AR®,

попробуй вот этот вариант как

 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
__int32 fa(unsigned __int64 _a, unsigned __int64 _b)
{
	_b += 0xFFFFFFFF;
	unsigned __int32 a_H = _a >> 32;
	unsigned __int32 a_L = _a & 0xFFFFFFFF;
	unsigned __int32 b_H = _b >> 32;
	unsigned __int32 b_L = _b & 0xFFFFFFFF;

	unsigned __int32 _ret = 0;
	unsigned __int32 d_H, d_L, c_H, c_L;

	__asm
	{
		mov		ecx, 0		// <edx:ecx> = d, начальное состояние = 000..01
		mov		edx, 0
		mov		eax, b_L	// <ebx:eax> = c, начальное состояние = 000..00
		mov		ebx, b_H
.align 16
		loopstart :
			inc		ecx
			xor		esi, esi	// <esi:edi> - будет заполняться в ходе работы либо 000..00, либо a
			xor		edi, edi

			shrd	ecx, edx, 1	// сдвиг младшей половины d
			cmovc	esi, a_H	// если был перенос в shrd, кладём a_H
			cmovc	edi, a_L	// если был перенос в shrd, кладём a_L
			shr		edx, 1		// сдвиг старшей половины d
			xor		edx, esi	// xor d либо с 000..00, либо с a
			xor		ecx, edi

			sub		eax, 1  		// декремент c
			sbb 	ebx, 0
			jz		loopout      
		test_d :						// метка не используется // проверка d == 1
			dec		ecx
			jnz		loopstart
			test	edx, edx
			jnz		loopstart
			inc		ecx
			jmp		asmout

		loopout :
			test	edx, edx
			jne		asmout
			cmp		ecx, 1
			jne		asmout
			mov		_ret, 1		// если прошли все 4 проверки выше, заполняем _ret = 1 (при объявлении _ret = 0)

		asmout:
			mov		d_H, edx	// сохраняем d для вывода в printf()...
			mov		d_L, ecx

			sub		eax, 0xFFFFFFFF
			sbb 	ebx, 0
			mov		c_H, ebx	// сохраняем c для вывода в printf()...
			mov		c_L, eax
	}
	_b -= 0xFFFFFFFF;
	printf("\nasmout:	d_H = %u		d_L = %u			c_H = %u		c_L = %u	\n", d_H, d_L, c_H, c_L);

	return _ret;
}

...
Рейтинг: 0 / 0
09.06.2018, 18:40
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659085
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
kealon(Ruslan)AR®, попробуй вот этот вариант

Попробовал, но только, к сожалению, на другом компе: С++ - 30 сек., мой асм - 80 сек., Ваш - 53 сек.
...
Рейтинг: 0 / 0
09.06.2018, 19:51
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659155
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®,

нет в мире таких крепостей, которые не взять за 529 секунд на i7-7700, используя Delphi+BASM
 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
//Aleksandr Sharahov 2018
function IsMaxLFSR(Feedback, MaxPeriod: pint64): boolean;
asm
  push ebp
  push ebx
  push esi

  mov ebx, dword ptr [edx]     //period
  mov ebp, dword ptr [edx+4]   //period

  mov ecx, dword ptr [eax]     //reverse feedback bits
  rol ecx, 16
  mov edx, ecx
  and edx, $FF00FF00
  xor ecx, edx
  shl ecx, 8
  shr edx, 8
  or  ecx, edx
  mov edx, ecx
  and edx, $F0F0F0F0
  xor ecx, edx
  shl ecx, 4
  shr edx, 4
  or  ecx, edx
  mov edx, ecx
  and edx, $CCCCCCCC
  xor ecx, edx
  shl ecx, 2
  shr edx, 2
  or  ecx, edx
  mov edx, ecx
  and edx, $AAAAAAAA
  xor ecx, edx
  shl ecx, 1
  shr edx, 1
  or  ecx, edx
  push ecx

  mov ecx, dword ptr [eax+4]   //reverse feedback bits
  rol ecx, 16
  mov edx, ecx
  and edx, $FF00FF00
  xor ecx, edx
  shl ecx, 8
  shr edx, 8
  or  ecx, edx
  mov edx, ecx
  and edx, $F0F0F0F0
  xor ecx, edx
  shl ecx, 4
  shr edx, 4
  or  ecx, edx
  mov edx, ecx
  and edx, $CCCCCCCC
  xor ecx, edx
  shl ecx, 2
  shr edx, 2
  or  ecx, edx
  mov edx, ecx
  and edx, $AAAAAAAA
  xor ecx, edx
  shl ecx, 1
  shr edx, 1
  or  ecx, edx
  push ecx

  xor esi, esi                 //initial state
  mov eax, $80000000           //initial state

@loop:
  sub ebx, 1                   //decrement period
  sbb ebp, 0                   //decrement period
  cdq                          //output bit to mask
  mov ecx, edx                 //output bit to mask
  add esi, esi                 //shift
  adc eax, eax                 //shift
  and ecx, dword ptr[esp]      //feedback
  and edx, dword ptr[esp+4]    //feedback
  xor esi, ecx                 //new state
  xor eax, edx                 //new state
  mov edx, eax                 //is equal
  xor edx, $80000000           //to
  or  edx, esi                 //initial state?
  jnz @loop
  or  ebx, ebp                 //is period maximal?
  setz al
  movzx eax, al
  add esp, 8
  pop esi
  pop ebx
  pop ebp
  end;

...
Рейтинг: 0 / 0
10.06.2018, 00:43
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659168
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
чего то пока далековато до моих 160-180с, которые достигаются одной строчкой =)
...
Рейтинг: 0 / 0
10.06.2018, 02:31
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659176
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
то ли еще будет )
...
Рейтинг: 0 / 0
10.06.2018, 07:26
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659197
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Сравнение состояния по частям дает 470.5 sec на i7-7700
 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
//Aleksandr Sharahov 2018
function IsMaxLFSR3(Feedback, MaxPeriod: pint64): boolean;
asm
  push ebp
  push ebx
  push esi

  mov ebx, dword ptr [edx]     //period
  mov ebp, dword ptr [edx+4]   //period

  mov ecx, dword ptr [eax]     //reverse feedback bits
  rol ecx, 16
  mov edx, ecx
  and edx, $FF00FF00
  xor ecx, edx
  shl ecx, 8
  shr edx, 8
  or  ecx, edx
  mov edx, ecx
  and edx, $F0F0F0F0
  xor ecx, edx
  shl ecx, 4
  shr edx, 4
  or  ecx, edx
  mov edx, ecx
  and edx, $CCCCCCCC
  xor ecx, edx
  shl ecx, 2
  shr edx, 2
  or  ecx, edx
  mov edx, ecx
  and edx, $AAAAAAAA
  xor ecx, edx
  shl ecx, 1
  shr edx, 1
  or  ecx, edx
  push ecx

  mov ecx, dword ptr [eax+4]   //reverse feedback bits
  rol ecx, 16
  mov edx, ecx
  and edx, $FF00FF00
  xor ecx, edx
  shl ecx, 8
  shr edx, 8
  or  ecx, edx
  mov edx, ecx
  and edx, $F0F0F0F0
  xor ecx, edx
  shl ecx, 4
  shr edx, 4
  or  ecx, edx
  mov edx, ecx
  and edx, $CCCCCCCC
  xor ecx, edx
  shl ecx, 2
  shr edx, 2
  or  ecx, edx
  mov edx, ecx
  and edx, $AAAAAAAA
  xor ecx, edx
  shl ecx, 1
  shr edx, 1
  or  ecx, edx
  push ecx

  xor esi, esi                 //initial state
  mov eax, $80000000           //initial state

@loop:
  sub ebx, 1                   //decrement period
  sbb ebp, 0                   //decrement period
  cdq                          //output bit to mask
  mov ecx, edx                 //output bit to mask
  add esi, esi                 //shift
  adc eax, eax                 //shift
  and ecx, dword ptr[esp]      //feedback
  and edx, dword ptr[esp+4]    //feedback
  xor esi, ecx                 //new state
  xor eax, edx                 //new state
  cmp eax, $80000000           //is equal to
  jne @loop
  test esi, esi                //initial state?
  jnz @loop
  or  ebx, ebp                 //is period maximal?
  setz al
  movzx eax, al
  add esp, 8

  pop esi
  pop ebx
  pop ebp
  end;

...
Рейтинг: 0 / 0
10.06.2018, 10:42
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659199
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
529 с, 160-180 с - в обоих случаях речь идёт про тест, где 254 числа и из них 20 f()==1 ?
...
Рейтинг: 0 / 0
10.06.2018, 10:49
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659214
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Aleksandr Sharahovто ли еще будет )
А Делфи позволяют посмотреть, во что ассемблерное превратил компилятор ассемблер в исходнике? В MS VC бывают незначительные отличия типа je вместо jz и т.п.
...
Рейтинг: 0 / 0
10.06.2018, 11:49
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659222
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
AR®je вместо jz
Это разные мнемоники одной и той же машиной команды
...
Рейтинг: 0 / 0
10.06.2018, 12:06
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659227
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®529 с, 160-180 с - в обоих случаях речь идёт про тест, где 254 числа и из них 20 f()==1 ?

У меня все по-честному, без параллелей.

Кстати простыню можно немного сократить.
И второй цикл лучше выравнивать, если компилятор позволяет, - будет еще быстрее (477 сек).
 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
//Aleksandr Sharahov 2018
function IsMaxLFSR4(Feedback, MaxPeriod: pint64): boolean;
asm
  push ebp
  push ebx
  push esi

  mov ebx, dword ptr [edx]     //period
  mov ebp, dword ptr [edx+4]   //period

  xor esi, esi
@reverse:
  mov ecx, dword ptr [eax+esi] //reverse feedback bits
  bswap ecx
  mov edx, ecx
  and edx, $F0F0F0F0
  xor ecx, edx
  shl ecx, 4
  shr edx, 4
  or  ecx, edx
  mov edx, ecx
  and edx, $CCCCCCCC
  xor ecx, edx
  shl ecx, 2
  shr edx, 2
  or  ecx, edx
  mov edx, ecx
  and edx, $AAAAAAAA
  xor ecx, edx
  shl ecx, 1
  shr edx, 1
  or  ecx, edx
  push ecx

  test esi, esi
  lea esi, [esi+4]
  jz @reverse

  xor esi, esi                 //initial state
  mov eax, $80000000           //initial state
  cdq                          //output bit to mask
  mov ecx, edx                 //output bit to mask

@loop:
  add esi, esi                 //shift
  adc eax, eax                 //shift
  and edx, dword ptr[esp+4]    //feedback
  and ecx, dword ptr[esp]      //feedback
  add ebx, -1                  //decrement period
  adc ebp, -1                  //decrement period
  xor eax, edx                 //new state
  xor esi, ecx                 //new state
  cdq                          //output bit to mask
  mov ecx, edx                 //output bit to mask
  cmp eax, $80000000           //is equal to
  jne @loop
  test esi, esi                //initial state?
  jnz @loop

  or  ebx, ebp                 //is period maximal?
  setz al
  movzx eax, al
  add esp, 8
  pop esi
  pop ebx
  pop ebp
  end;

...
Рейтинг: 0 / 0
10.06.2018, 12:38
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659229
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Aleksandr Sharahov,

опечатка: не 477, а 447 сек
...
Рейтинг: 0 / 0
10.06.2018, 12:46
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659318
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Aleksandr Sharahov

Хотел потестить Ваши примеры, но, похоже, в C++ нельзя использовать ebp для собственных нужд. Компилируется с warning'ами, а при запуске падает на первом mov ebp.

Есть более фундаментальный вопрос: откуда уверенность, что initial state обязательно повторится? У Вас его повторение является единственным условием выхода из цикла, а в исходном алгоритме ещё и достижение предела счётчиком цикла.
Возможно, повторение initial state неизбежно, но я не знаю, так ли это. Вы, возможно знаете теорию.
...
Рейтинг: 0 / 0
10.06.2018, 19:45
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659324
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®Хотел потестить Ваши примеры, но, похоже, в C++ нельзя использовать ebp для собственных нужд. Компилируется с warning'ами, а при запуске падает на первом mov ebp.

В последних функциях регистр edi не используется. Замените.

AR®Есть более фундаментальный вопрос: откуда уверенность, что initial state обязательно повторится? У Вас его повторение является единственным условием выхода из цикла, а в исходном алгоритме ещё и достижение предела счётчиком цикла.
Возможно, повторение initial state неизбежно, но я не знаю, так ли это. Вы, возможно знаете теорию.
Вы бы не задавали этот вопрос, если бы грызли гранит до основания, а не чисто периодически )
Но, как мы помним, эту "Задачу должен решить я" (с).
...
Рейтинг: 0 / 0
10.06.2018, 20:42
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659325
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
AR®Увы. Для 32 бит всё уже успешно проделано. И 33-й - это только начало и почва для отладки.

Нет ли идей, что у меня ломает конвейер?
Идей нет. Конвейер команд ломают условные переходы. Но в нашем случае 99% переходов - назад.
Как определить состояние конвейера в нашем случае - ХЗ. У меня нет мыслей. Самое правильное - это
воспользоваться утилитой тонкого тюнинга Intel Vtune и посмотреть ее отчоты.

Я по ссылкам от этого топика пошёл читать про PAPI. Не думаю что выйду с предложением. Тут Шарахов
тебе хорошо помогает. А я уже свои мысли сказал. Если-б я делал эту функцию - то использовал-бы
мемоизацию.
...
Рейтинг: 0 / 0
10.06.2018, 20:52
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659331
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
Aleksandr SharahovВы бы не задавали этот вопрос, если бы грызли гранит до основания, а не чисто периодически )
Э-э, я-то делаю это скорее даже а периодически. ))

Aleksandr SharahovНо, как мы помним, эту "Задачу должен решить я" (с).
И решу, не сумневайтесь. )
...
Рейтинг: 0 / 0
10.06.2018, 21:14
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659344
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®Aleksandr SharahovВы бы не задавали этот вопрос, если бы грызли гранит до основания, а не чисто периодически )
Э-э, я-то делаю это скорее даже а периодически. ))

Главное, все читать внимательно, чтоб случайно не пропустить идею какую или подсказку )


AR®Aleksandr SharahovНо, как мы помним, эту "Задачу должен решить я" (с).
И решу, не сумневайтесь. )
Подкину еще дровишек (191 сек на i7-7700). Решать - не перерешать )
 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
type
  i64= array[0..1] of cardinal;
  ca= ^i64;
const
  RunCount= 8*1024; // = 2^N, N>=3
var
  XorTable: array[0..255] of int64;
  RunTable: array[0..RunCount-1] of int64;
  RunOver: array[0..RunCount-1] of integer;

procedure FillXorTable(Feedback: pint64);
var
  i, Run: integer;
  x: int64;
  IsOdd: boolean;
begin;
  for i:=0 to 255 do begin;
    x:=i;
    for Run:=1 to 8 do begin;
      IsOdd:=x and 1<>0;
      x:=x shr 1;
      if IsOdd then x:=x xor Feedback^;
      end;
    XorTable[i]:=x;
    end;
  end;

procedure FillRunTable(Feedback: pint64);
var
  Run: integer;
  x: int64;
  IsOdd: boolean;
begin;
  x:=1;
  RunTable[0]:=x;
  RunOver[0]:=0;
  for Run:=1 to RunCount-1 do begin;
    IsOdd:=x and 1<>0;
    x:=x shr 1;
    if IsOdd then x:=x xor Feedback^;
    RunTable[Run]:=x;
    RunOver[Run]:=Run;
    end;
  end;

procedure SortRunTable;
var
  i, j, t: integer;
  x: int64;
begin;
  i:=0;
  j:=RunCount-1;
  while j>0 do begin;
    if ca(@RunTable[j])[0]<ca(@RunTable[i])[0] then i:=j;
    dec(j);
    end;
  if i>0 then begin;
    x:=RunTable[0]; RunTable[0]:=RunTable[i]; RunTable[i]:=x;
    t:=RunOver[0]; RunOver[0]:=RunOver[i]; RunOver[i]:=t;
    end;

  j:=1;
  while true do begin;
    if j>=RunCount-1 then break;
    inc(j);
    if ca(@RunTable[j])[0]<ca(@RunTable[j-1])[0] then begin;
      x:=RunTable[j];
      t:=RunOver[j];
      i:=j;
      repeat;
        RunTable[i]:=RunTable[i-1];
        RunOver[i]:=RunOver[i-1];
        dec(i);
        until not (ca(@x)[0]<ca(@RunTable[i-1])[0]);
      RunTable[i]:=x;
      RunOver[i]:=t;
      end;
    end;
  end;

function FindRunOver(p: pint64): integer;
var
  Left, Right: integer;
begin;
  Left:=0;
  Right:=RunCount;              //index of the element greater than p^
  while Left<Right do begin;
    Result:=(Left+Right) shr 1; //round to left
    if ca(p)[0]<ca(@RunTable[Result])[0] then Right:=Result else Left:=Result+1;
    end;
  dec(Right);
  while (Right>=0)
  and (ca(p)[0]=ca(@RunTable[Right])[0]) do begin;
    if ca(p)[1]=ca(@RunTable[Right])[1] then begin;
      Result:=RunOver[Right];
      exit;
      end;
    dec(Right);
    end;
  Result:=-1;
  end;

procedure RunLFSR(var x: int64);
var
  i, j: integer;
begin;
  j:=RunCount;
  repeat;
    i:=x and 255;
    x:=x shr 8 xor XorTable[i];
    j:=j-8;
    until j<=0;
  end;

//Aleksandr Sharahov 2018
function IsMaxLFSR5(Feedback, MaxPeriod: pint64): boolean;
var
  Count, State: int64;
  Over: integer;
begin;
  if (MaxPeriod^<MaxInt)
  or (MaxPeriod^ and (MaxPeriod^+1)<>0) then begin;
    Result:=false;
    exit;
    end;
  FillXorTable(Feedback);
  FillRunTable(Feedback);
  SortRunTable;
  Count:=0;
  State:=1;
  repeat;
    RunLFSR(State);
    Count:=Count+RunCount;
    Over:=FindRunOver(@State);
    until Over>=0;
  Result:=Count=MaxPeriod^+Over;
  end;



Написано неоптимально, просто демонстрация идеи.
Алгоритм каждой из процедур можно улучшить + использовать ассемблер.

Еще больше оптимизаций можно подсмотреть здесь:
http://guildalfa.ru/alsha/node/2
http://guildalfa.ru/alsha/node/4
http://guildalfa.ru/alsha/node/10
...
Рейтинг: 0 / 0
10.06.2018, 22:37
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659350
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
AR®Aleksandr Sharahov

Хотел потестить Ваши примеры, но, похоже, в C++ нельзя использовать ebp для собственных нужд. Компилируется с warning'ами, а при запуске падает на первом mov ebp.

Есть более фундаментальный вопрос: откуда уверенность, что initial state обязательно повторится? У Вас его повторение является единственным условием выхода из цикла, а в исходном алгоритме ещё и достижение предела счётчиком цикла.
Возможно, повторение initial state неизбежно, но я не знаю, так ли это. Вы, возможно знаете теорию.
если грубо перевести
 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
__int32 fSharahov(unsigned __int64 _a, unsigned __int64 _b)
{
	unsigned __int32 _ret = 0;
	_asm {
		push ebp
		push ebx
		push esi
		push edi

		lea eax, _a
		lea edx, _b

		//
		mov ebx, dword ptr[edx]     //period
		mov ebp, dword ptr[edx + 4]   //period

		xor esi, esi
	reverse:
		mov ecx, dword ptr[eax + esi] //reverse feedback bits
		bswap ecx
		mov edx, ecx
		and edx, 0xF0F0F0F0
		xor ecx, edx
		shl ecx, 4
		shr edx, 4
		or ecx, edx
		mov edx, ecx
		and edx, 0xCCCCCCCC
		xor ecx, edx
		shl ecx, 2
		shr edx, 2
		or ecx, edx
		mov edx, ecx
		and edx, 0xAAAAAAAA
		xor ecx, edx
		shl ecx, 1
		shr edx, 1
		or ecx, edx
		push ecx

		test esi, esi
		lea esi, [esi + 4]
		jz reverse

		xor esi, esi                 //initial state
		mov eax, 0x80000000           //initial state
		cdq                          //output bit to mask
		mov ecx, edx                 //output bit to mask
	loop_cicle:
		add esi, esi                 //shift
		adc eax, eax                 //shift
		and edx, dword ptr[esp+4]    //feedback
		and ecx, dword ptr[esp]      //feedback
		add ebx, -1                  //decrement period
		adc ebp, -1                  //decrement period
		xor eax, edx                 //new state
		xor esi, ecx                 //new state
		cdq                          //output bit to mask
		mov ecx, edx                 //output bit to mask
		cmp eax, 0x80000000           //is equal to
		jne loop_cicle
		test esi, esi                //initial state?
		jnz loop_cicle

		or ebx, ebp                 //is period maximal?
		setz al
		
		add esp, 8
		///
		pop edi
		pop esi
		pop ebx
		pop ebp
		movzx eax, al
		mov _ret, eax
	}
	return _ret;
}

...
Рейтинг: 0 / 0
10.06.2018, 23:34
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659355
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
AR®,

вот только я что-то не вижу где у него счётчик проверяется, вижу что меняется, а что каждый раз проверяется - нет
...
Рейтинг: 0 / 0
11.06.2018, 00:03
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659358
AR®
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AR®
Участник
kealon(Ruslan)AR®,

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

Именно. Не проверяется вовсе. Только 1 раз в конце при принятии решения о возвращаемом значении.
Выше было по этому поводу:

Aleksandr SharahovAR®Есть более фундаментальный вопрос: откуда уверенность, что initial state обязательно повторится? У Вас его повторение является единственным условием выхода из цикла, а в исходном алгоритме ещё и достижение предела счётчиком цикла.
Возможно, повторение initial state неизбежно, но я не знаю, так ли это. Вы, возможно знаете теорию.
Вы бы не задавали этот вопрос, если бы грызли гранит до основания, а не чисто периодически )
Но, как мы помним, эту "Задачу должен решить я" (с).
...
Рейтинг: 0 / 0
11.06.2018, 00:16
| Ответить | Цитировать | Написать  
Ассемблер - регистры MMX - команды условного перехода.
    #39659567
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
AR®, как движется изучение?

Сейчас проверил, таблица на 2K значений, как в статье по CRC32,
позволяет прогнать длинный тест менее, чем за 66 сек.
Чистый паскаль, без других оптимизаций.
...
Рейтинг: 0 / 0
12.06.2018, 01:20
| Ответить | Цитировать | Написать  
25 сообщений из 225, страница 8 из 9
  8  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Ассемблер - регистры MMX - команды условного перехода.
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]