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

;
; Подпрограмма RANDOM
;
; Генерирует случайные числа с использованием 25-битного регистра сдвига
; с обратными связями XOR от 7 и 25 разрядов (что определяет максимальную
; длину цикла).
;
; Для корректного применения подпрограммы учитывайте следующее:
; A) Некоторое ненулевое стартовое значение (SEED) обязательно должно
; быть предварительно загружено в RN1.
; B) Последовательность генерируемых данных будет повторена после 
; приблизительно 33 миллиона вызова подпрограммы.
;
; Требуемые для работы ресурсы CPU:
;
; 6 ячеек памяти RAM для следующий целей.
;
; RANNUM: вычисленное случайное число
; RN1-RN1: эти ячейки формируют регистр сдвига
; TEMP1: регистр для временного хранения данных.
;
; Подпрограмма разрушает содержимое регистра A (аккумулятор) и бита
; переноса (CARRY BIT).;
;
RANDOM: MOV     A,RN4     ; Бит 25 помещается в CARRY
        RRC     A
        MOV     RN4,RN3
        MOV     RN3,RN2
        MOV     RN2,RN1   ; Сдвиг влево всех байт
        MOV     A,RN4     ; был RN3
        RRC     A         ; получение бита 25 (в бите CARRY) в старом RN3
        MOV     TEMP1,A   ; сохранение для последующего использования
        MOV     A,RN1
        RLC     A         ; бит 1 в позицию 7
        MOV     RN1,A     ; вернуть обратно
        MOV     A,TEMP1   ; восстановление A
        XRL     A,RN1     ; сумма по модулю 2 всех битов в RN1 и бита CARRY
        MOV     TEMP1,A   ; сохранение A
        MOV     A,RN4
        RRC     A
        MOV     RN4,A     ; сдвиг RN4
        MOV     A,RN3
        RRC     A
        MOV     RN3,A     ; сдвиг RN3
        MOV     A,RN2
        RRC     A
        MOV     RN2,A     ; сдвиг RN2
        MOV     A,TEMP1   ; восстановление A
        RLC     A
        MOV     RN1,A     ; xor перезаписывает все 8 бит, но это не имеет значения
        MOV     RANNUM,A  ; случайное число!!
        RET

  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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171

// Макрос для генерации 32-разрядной битовой маски.
#define _BVD( x ) ((uint32_t)( 1 ) << ( x ))

/*
 * Подпрограмма генерации случайного байта с использованием 32-bit LFSR
 */
uint8_t random_byte_lfsr32(void)
{
    // регистр сдвига
    static uint32_t lfsr = 0xDEADBEEF;
    
    // сдвиг через 8 состояний для получения совершенно нового байта
    uint8_t state;

    for (state = 0; state <= 8; state++)
    {
        uint8_t new_bit = 0;

#ifndef OPTIMIZED_LFSR32

/*
 * Оригинальный код на C.
 * В среднем 61175.8 циклов на update_output_arcing() с опцией -O2, max частота
 * обновления ~250 Гц, на частоте обновления 60 Гц CPU загружен ~24%.
 */
        // xor всех разрядов tap в один бит
        if ( lfsr & _BVD(1) )
            new_bit ^= 1;
        if ( lfsr & _BVD(5) )
            new_bit ^= 1;
        if ( lfsr & _BVD(6) )
            new_bit ^= 1;
        if ( lfsr & _BVD(31) )
            new_bit ^= 1;
        // сдвиг в новый бит
        lfsr >>= 1 ;
        lfsr |= (uint32_t)( new_bit ) << 31;

#else

/*
 * Оптимизированная вручную версия на ассемблере.
 * В среднем 13697.0 циклов на update_output_arcing() с опцией -O2, max частота
 * обновления ~1200 Гц, на частоте обновления 60 Гц загрузка CPU ~5%.
 */

/*
 * Безвозмездно предоставлен подробный комментарий по работе этой версии.
 *
 * Мотивацией для разработки был тот факт, что для 32-битных операций
 * сдвига на C компилятор GCC AVR текущих версий генерирует поистине
 * ужасающий машинный код, с различными сдвигами и ненужными промежуточными
 * операциями хранения, в то время как все можно было просто реализовать
 * 4 инструкциями, передающими данные через бит переноса (carry flag.
 *
 * Вычисление нового бита GCC реализовывал из кода C не настолько плохо,
 * но все равно лучше это было сделать на ассемблере вручную.
 */
        asm volatile(
/*
 * Операция xor над разрядами tap, результат помещается в new_bit.
 *
 * "sbrc a b" означает пропуск следующей инструкции, если очищен бит b
 * в регистре a. Такой условный переход сделан для каждого разряда
 * обратной связи (tap) в регистре lfsr. Если бит tap установлен,
 * ветвление не выполняется, и далее выполняется команда "eor",
 * которая переключает младший бит в new_bit операцией xor с константой
 * 0x01 в регистре 4.
 */
            "sbrc %a0, 1"                                  "\n\t"
            "eor %1, %4"                                   "\n\t"
            "sbrc %a0, 5"                                  "\n\t"
            "eor %1, %4"                                   "\n\t"
            "sbrc %a0, 6"                                  "\n\t"
            "eor %1, %4"                                   "\n\t"
            "sbrc %d0, 7"                                  "\n\t"
            "eor %1, %4"                                   "\n\t"

/*
 * Сдвиг вправо значения lfsr.
 *
 * Сдвиг начинается операции правого сдвига младшего байта слова,
 * которая выдвигает младший бит слова в бит переноса, и при этом
 * очищает старший бит. Затем используется "ror" над остальными
 * тремя байтами, которые сдвигают данные вправо через бит переноса.
 * Отличие сдвига "ror" от сдвига "lsr" в том, что "ror" вдвигает
 * флаг переноса в старший бит вместо очистки старшего бита. При сдвиге
 * первого байта не нужно вдвигать бит переноса, поэтому используется
 * команда "lsr". Далее флаг переноса используется для передачи
 * младшего бита предыдущего байта в старший бит текущего байта.
 */
            "lsr %d0"                                      "\n\t"
            "ror %c0"                                      "\n\t"
            "ror %b0"                                      "\n\t"
            "ror %a0"                                      "\n\t"

/*
 * Вставка нового бита.
 *
 * Младший бит ячейки new_bit хранит значение нового бита. Если он очищен,
 * то следующая инструкция пропускается. В следующей инструкции старший
 * бит в старшем байте регистра устанавливается путем операции OR с
 * константой 0x80.
 */
            "sbrc %1, 0"                                   "\n\t"
            "ori %d0, %5"                                  "\n\t"

/****************************************************/

/*
 * Выходные регистры.
 *
 * 0 = lfsr
 * 1 = new_bit
 *
 * Компилятору gcc будет указано, что lfsr имеет тип uint32_t, что 
 * размещение этой переменной в четырех (вероятно расположенных в памяти
 * последовательно друг за другом) регистрах общего назначения (General
 * Purpose Register, GPR), к которым происходит обращение по именам
 * от %d0 до %a0.
 */
            : "=r" ( lfsr ), "=d" ( new_bit )

/*
 * Входные регистры.
 *
 * 0 = lfsr
 * 1 = new_bit
 * 4 = регистр для константы
 * 5 = непосредственная константа (immediate constant)
 *
 * 4 является константой, которая появляется в коде загруженной в регистр.
 * 5 является непосредственной константой, она встроена прямо в код, это
 * не регистр. 2 и 3 пропущены, потому что "входной" lfsr и new_bit должны
 * быть там, но они повторно переназначены на 0 и 1, поскольку означают
 * то же самое. Это обычное неочевидное поведение gcc.
 */
            : "0" ( lfsr ), "1" ( new_bit ), "d" ( 0x01 ), 
                "m" ( 0x80 )
            );
#endif
    }
    // возврат младшего байта
    return (uint8_t)( lfsr & 0xFF );
}

/*
 * Генерация случайного байта x так, что min < = x < = max.
 */
int8_t random_byte_in(int8_t min, int8_t max)
{
    // Получение случайного байта из младшего байта слова.
    uint16_t a_random_byte = random_byte_lfsr32();
    // Масштабирование.
    a_random_byte *= (max - min + 1);
    // Транслирование и возврат.
    return (int8_t)( (a_random_byte >> 8) + min );
}

/*
 * Генерация случайного байта x так, что min < = x < = max
 */
uint8_t random_ubyte_in(uint8_t min, uint8_t max)
{
    // Получение случайного байта из младшего байта слова.
    uint16_t a_random_byte = random_byte_lfsr32();
    // Масштабирование.
    a_random_byte *= (max - min + 1);
    // Транслирование и возврат.
    return (uint8_t)( (a_random_byte >> 8) + min );
}