Xiao S3 Sense Generator liczb (prawie) losowych

H1M4W4R1 · 5 lutego

Wstęp

Na fali wątku o grze bingo powstała wielka dyskusja o losowości i generatorach liczb losowych i pseudolosowych (jak rand() w C). Do tego YouTube zaczął mi polecać filmiki o liczbach losowych i uznałem to za znak, że warto zbudować własny generator liczb (prawie) losowych. W artykule wykorzystałem moduły otrzymane w ramach współpracy z Botlandem.

Może nie używałbym go do generowania kodów odpalających głowice atomowe, ale do prostych gier na ESP32 się jak najbardziej nadaje.

Rozkład prawdopodobieństwa po 3878 losowaniach liczb z zakresu 0 do 4.

Elektronika i zasada działania

Urządzenie jest niezwykle skomplikowane - jest to płytka Xiao ESP32 S3 Sense i przewód USB-C. Raczej każdy da radę zbudować (nawet nie potrzeba banana, chociaż wersja z bananem generuje lepsze wyniki niż ten generator).

Xiao ESP32 S3 Sense wraz z zasłoniętą kamerą

Założeniem systemu jest to, iż kamera posiada szum własny (jak dobrze, że fizyka nas nie lubi i utrudnia nam życie, czasem można to wykorzystać dla własnych potrzeb). Tj. kiedy zasłonimy obiektyw np. taśmą izolacyjną (czerwona zwiększa prędkość działania urządzenia, ale czarna generuje szerszy zakres losowości) kamera generuje obraz, który nie jest całkowicie czarny tylko zawiera jaśniejsze artefakty.

Obraz z zasłoniętej kamery

Tym samym możemy wykorzystać dane z czujnika i nieco matematyki, by zamienić te dane na liczbę.

Problem z stałymi częściami obrazu

Jeżeli kiedykolwiek zasłanialiście obiektyw kamery zauważyliście, że część obrazu się nie zmienia (zawsze wygląda tak samo). Tak również jest w naszym przypadku, a przy liczbach losowych wprowadzałoby to zaburzenia rozkładu prawdopodobieństwa (można też powiedzieć 'bias'). Możemy łatwo to obejść używając operacji XOR do porównania dwóch ramek pobranych z kamery by usunąć składowe stałe.

Konfiguracja PlatformIO

Cały projekt został zaimplementowany z użyciem PlatformIO i frameworka Arduino (by sobie ułatwić życie). Jako, że płytka posiada PSRAM został on aktywowany (UWAGA: profil PlatformIO pod płytkę Xiao jest błędny i ma wpisane, że PSRAM używa QSPI, gdy w rzeczywistości jest to OSPI).

[env:seeed_xiao_esp32s3]
platform = espressif32
board = seeed_xiao_esp32s3
framework = arduino
build_flags =
    -DARDUINO_USB_CDC_ON_BOOT=1
    -DBOARD_HAS_PSRAM
    -DPREFER_PSRAM
    -mfix-esp32-psram-cache-issue

board_build.arduino.memory_type = qio_opi

Konfiguracja płytki z PSRAM

Kod programu

#include <Arduino.h>
#include "esp_camera.h"

#define PWDN_GPIO_NUM  (-1)
#define RESET_GPIO_NUM (-1)
#define XCLK_GPIO_NUM  10
#define SIOD_GPIO_NUM  40
#define SIOC_GPIO_NUM  39

#define Y9_GPIO_NUM    48
#define Y8_GPIO_NUM    11
#define Y7_GPIO_NUM    12
#define Y6_GPIO_NUM    14
#define Y5_GPIO_NUM    16
#define Y4_GPIO_NUM    18
#define Y3_GPIO_NUM    17
#define Y2_GPIO_NUM    15
#define VSYNC_GPIO_NUM 38
#define HREF_GPIO_NUM  47
#define PCLK_GPIO_NUM  13

bool camera_ready = false; // Pozwala sprawdzić czy kamera jest gotowa

#define N_MAX_VALUE 5 // Liczba wiaderek (maksymalna liczba do wylosowania)
uint32_t sampleCounts[N_MAX_VALUE]; // Liczba losowań konkretnej liczby
uint64_t samplesCount = 0;          // Liczba łącznych losowań

void setup()
{
    delay(2000);
    Serial.begin(115200);
    while (!Serial) // Poczekaj na uruchomienie portu szeregowego
    {
        Serial.print(".");
    }

    Serial.println("Serial port ready!");

    // Konfiguracja kamery dla Xiao ESP32-S3 Sense
    camera_config_t config;

    // IO
    config.ledc_channel = LEDC_CHANNEL_0;
    config.ledc_timer   = LEDC_TIMER_0;
    config.pin_d0       = Y2_GPIO_NUM;
    config.pin_d1       = Y3_GPIO_NUM;
    config.pin_d2       = Y4_GPIO_NUM;
    config.pin_d3       = Y5_GPIO_NUM;
    config.pin_d4       = Y6_GPIO_NUM;
    config.pin_d5       = Y7_GPIO_NUM;
    config.pin_d6       = Y8_GPIO_NUM;
    config.pin_d7       = Y9_GPIO_NUM;
    config.pin_xclk     = XCLK_GPIO_NUM;
    config.pin_pclk     = PCLK_GPIO_NUM;
    config.pin_vsync    = VSYNC_GPIO_NUM;
    config.pin_href     = HREF_GPIO_NUM;
    config.pin_sccb_sda = SIOD_GPIO_NUM;
    config.pin_sccb_scl = SIOC_GPIO_NUM;
    config.pin_pwdn     = PWDN_GPIO_NUM;
    config.pin_reset    = RESET_GPIO_NUM;

    config.xclk_freq_hz = 20000000;            // Częstotliwość komunikacji
    config.frame_size   = FRAMESIZE_240X240;   // Pakiet danych o małym rozmiarze (szybkie liczenie)
    config.pixel_format = PIXFORMAT_GRAYSCALE; // Dla łatwiejszej obróbki
    config.grab_mode    = CAMERA_GRAB_LATEST;  // Dla lepszej losowości
    config.fb_location  = CAMERA_FB_IN_DRAM;   // Można zmienić też na CAMERA_FB_IN_PSRAM, ale jest wolniejszy :(
    config.fb_count     = 2;

    // Inicjalizacja kamery
    const esp_err_t err = esp_camera_init(&config);
    if (err != ESP_OK)
    {
        Serial.printf("Camera init failed with error 0x%x", err);
        return;
    }

    // Jesteśmy gotowi do działania
    Serial.println("Camera ready!");
    camera_ready = true;
}


// Generuje losową liczbę używając kamery
uint32_t generate_random_number()
{
    // Zrób dwa "zdjęcia" kamerą i upewnij się, że są poprawne
    camera_fb_t* fb0 = esp_camera_fb_get();
    camera_fb_t* fb1 = esp_camera_fb_get();
    if (!fb0 || !fb1)
    {
        Serial.println("Failed to get camera frame buffer"); // Błąd odczytu kamery
        return 0xFFFFFFFF;
    }

    // Zmienna zawierająca rezultat losowania
    uint32_t result = 1;

    // Oblicz losową liczbę uwzględniając cały bufor z oveflowem
    for (uint32_t index = 0; index <= fb0->len; index++)
    {
        // Operacja XOR automatycznie usuwa wszystkie powtarzające się fragmenty pobrane przez kamerę,
        // które występują najczęściej na rogach.
        result += fb0->buf[index] ^ fb1->buf[index];
    }

    // Zwróć bufory do kamery
    esp_camera_fb_return(fb0);
    esp_camera_fb_return(fb1);

    return result;
}


void loop()
{
    // Poczekaj aż kamera będzie gotowa
    if (camera_ready)
    {
        // Wylosuj liczbę i dodaj do odpowiedniego wiaderka
        const uint32_t rnd = generate_random_number();
        sampleCounts[rnd % N_MAX_VALUE]++;
        samplesCount++;

        // Policz rozkład liczb w wiaderkach
        for (int n = 0; n < N_MAX_VALUE; n++)
        {
            if (n > 0) Serial.print(" | ");
            Serial.printf("%.2f", sampleCounts[n] / (float) samplesCount * 100);
            Serial.print("%");
        }

        // Zakończ linię wyświetlając liczbę próbek
        Serial.printf(" | Total: %llu\r\n", samplesCount);
    }
}

Najbardziej istotny jest fragment losowania, reszta to tylko otoczka pozwalająca przetestować działanie z wykorzystaniem monitora portu szeregowego. Na początku algorytm losowania liczby pobiera dwa bufory z kamery (można nazwać to potocznie zdjęciami) i upewnia się, że są one prawidłowe:

    // Zrób dwa "zdjęcia" kamerą i upewnij się, że są poprawne
    camera_fb_t* fb0 = esp_camera_fb_get();
    camera_fb_t* fb1 = esp_camera_fb_get();
    if (!fb0 || !fb1)
    {
        Serial.println("Failed to get camera frame buffer"); // Błąd odczytu kamery
        return 0xFFFFFFFF;
    }

Kolejnym etapem jest zsumowanie różnic pomiędzy obecną, a poprzednią klatką (i tutaj raczej nie jest to najlepszy algorytm, ale na ten moment nie mam lepszego pomysłu, który byłby akceptowalnie wydajny). Obecna wersja jest też dość mało losowa (prawidłowo powinienem sumować wartości pikseli, które się zmieniły, a nie różnice między pikselami w ramkach, ale wtedy wymagałoby to kosztownej operacji porównania, która nie zostałaby skompensowana przez branch prediction, gdyż nie byłoby po niej dostatecznie dużo prostych operacji zajmujących czas procesora gdy ten oblicza porównanie w tle).

    // Zmienna zawierająca rezultat losowania
    uint32_t result = 1;

    // Oblicz losową liczbę uwzględniając cały bufor z oveflowem
    for (uint32_t index = 0; index <= fb0->len; index++)
    {
        // Operacja XOR automatycznie usuwa wszystkie powtarzające się fragmenty pobrane przez kamerę,
        // które występują najczęściej na rogach.
        result += fb0->buf[index] ^ fb1->buf[index];
    }

A na koniec zwalniamy bufory do pobrania kolejnych zdjęć przez kamerę. Bez tego program wylosuje tylko jedną liczbę i zacznie wyrzucać błędy.

    // Zwróć bufory do kamery
    esp_camera_fb_return(fb0);
    esp_camera_fb_return(fb1);

Rozkład prawdopodobieństwa

Algorytm posiada bardzo dobry rozkład prawdopodobieństwa dla 10 000 sampli i do 10 liczb w zestawieniu. W przypadku 5 liczb i 10 000 sampli rozkład jest wysoce zbliżony do równomiernego.

Rozkład prawdopodobieństwa dla 5 liczb

1-1.5pp odchylenia między wartościami jest akceptowalne jak na tak prosty system, gdyż może ono wynikać z niedokładnego zasłonięcia obiektywu, nieuwzględnionych parametrów fizycznych, a szczególnie tego, że algorytm jest nie do końca idealny. Ten ostatni czynnik bardzo mocno wpływa na maksymalną wartość, którą możemy losować (około 10), a zwiększenie zakresu wymaga przeróbki algorytmu obliczającego wynik tak, by uwzględnić w nim wartości pikseli odczytane przez kamerę.

Ale do prostych losowań prawda-fałsz czy D6 algorytm nadaje się w sam raz.

W artykule wykorzystałem moduły otrzymane w ramach współpracy z Botlandem.

H1M4W4R1 · 6 lutego

Ciąg dalszy poprawiania algorytmu...

#include <Arduino.h>
#include "esp_camera.h"

#define PWDN_GPIO_NUM  (-1)
#define RESET_GPIO_NUM (-1)
#define XCLK_GPIO_NUM  10
#define SIOD_GPIO_NUM  40
#define SIOC_GPIO_NUM  39

#define Y9_GPIO_NUM    48
#define Y8_GPIO_NUM    11
#define Y7_GPIO_NUM    12
#define Y6_GPIO_NUM    14
#define Y5_GPIO_NUM    16
#define Y4_GPIO_NUM    18
#define Y3_GPIO_NUM    17
#define Y2_GPIO_NUM    15
#define VSYNC_GPIO_NUM 38
#define HREF_GPIO_NUM  47
#define PCLK_GPIO_NUM  13

bool camera_ready = false; // Pozwala sprawdzić czy kamera jest gotowa

#define N_MAX_VALUE 5 // Liczba wiaderek (maksymalna liczba do wylosowania)
uint32_t sampleCounts[N_MAX_VALUE]; // Liczba losowań konkretnej liczby
uint64_t samplesCount = 0;          // Liczba łącznych losowań

#define FRAME_SIZE_CAM FRAMESIZE_96X96
#define FRAME_SIZE (96 * 96)
uint8_t baseFrames[FRAME_SIZE * 3];

uint8_t is_frame_data_noisy(const uint32_t index)
{
    // Obliczenie indeksów dla ramek
    const uint32_t realIndex0 = FRAME_SIZE * 0 + index;
    const uint32_t realIndex1 = FRAME_SIZE * 1 + index;
    const uint32_t realIndex2 = FRAME_SIZE * 2 + index;

    // Analiza danych ramek - czy na danym polu wstępuje szum?
    return baseFrames[realIndex0] ^ baseFrames[realIndex1] ^ baseFrames[realIndex2];
}

void setup()
{
    delay(2000);
    Serial.begin(115200);
    while (!Serial) // Poczekaj na uruchomienie portu szeregowego
    {
        Serial.print(".");
    }

    Serial.println("Serial port ready!");

    // Konfiguracja kamery dla Xiao ESP32-S3 Sense
    camera_config_t config;

    // IO
    config.ledc_channel = LEDC_CHANNEL_0;
    config.ledc_timer   = LEDC_TIMER_0;
    config.pin_d0       = Y2_GPIO_NUM;
    config.pin_d1       = Y3_GPIO_NUM;
    config.pin_d2       = Y4_GPIO_NUM;
    config.pin_d3       = Y5_GPIO_NUM;
    config.pin_d4       = Y6_GPIO_NUM;
    config.pin_d5       = Y7_GPIO_NUM;
    config.pin_d6       = Y8_GPIO_NUM;
    config.pin_d7       = Y9_GPIO_NUM;
    config.pin_xclk     = XCLK_GPIO_NUM;
    config.pin_pclk     = PCLK_GPIO_NUM;
    config.pin_vsync    = VSYNC_GPIO_NUM;
    config.pin_href     = HREF_GPIO_NUM;
    config.pin_sccb_sda = SIOD_GPIO_NUM;
    config.pin_sccb_scl = SIOC_GPIO_NUM;
    config.pin_pwdn     = PWDN_GPIO_NUM;
    config.pin_reset    = RESET_GPIO_NUM;

    config.xclk_freq_hz = 20000000;            // Częstotliwość komunikacji
    config.frame_size   = FRAME_SIZE_CAM;     // Pakiet danych o małym rozmiarze (szybkie liczenie)
    config.pixel_format = PIXFORMAT_GRAYSCALE; // Dla łatwiejszej obróbki
    config.grab_mode    = CAMERA_GRAB_LATEST;  // Dla lepszej losowości
    config.fb_location  = CAMERA_FB_IN_PSRAM;  // Można zmienić też na CAMERA_FB_IN_PSRAM, ale jest wolniejszy :(
    config.fb_count     = 2;

    // Inicjalizacja kamery
    const esp_err_t err = esp_camera_init(&config);
    if (err != ESP_OK)
    {
        Serial.printf("Camera init failed with error 0x%x", err);
        return;
    }

    // Pobieramy trzy obrazki z kamery co pół sekundy
    for (int n = 0; n < 3; n++)
    {
        camera_fb_t* image = esp_camera_fb_get();
        memcpy(baseFrames + n * FRAME_SIZE, image, FRAME_SIZE);
        esp_camera_fb_return(image);
        delay(500);
    }

    // Jesteśmy gotowi do działania
    Serial.println("Camera ready!");
    camera_ready = true;
}


// Generuje losową liczbę używając kamery
uint32_t generate_random_number()
{
    // Pobierz bufory z kamery jeżeli nie istnieją
    camera_fb_t* last_buffer = esp_camera_fb_get();

    // Zmienna zawierająca rezultat losowania
    uint32_t result       = 0;
    uint8_t  bit_count = 0;

    // Oblicz losową liczbę uwzględniając cały bufor z oveflowem
    for (uint32_t index = 0; index <= last_buffer->len; index++)
    {
        // Pomiń ramki bez szumu
        if (!is_frame_data_noisy(index)) continue;

        // Pobierz dane z bufora i przypisz do rezultatu
        const uint8_t value = last_buffer->buf[index];
        result = (result << 1) | (value & 0x01);
        bit_count++;

        // Jeżeli mamy całą liczbę zakończ działanie
        if (bit_count == sizeof(uint32_t) * 8) break;
    }

    esp_camera_fb_return(last_buffer); // Zwróć przed-ostatni bufor

    return result;
}


void loop()
{
    // Poczekaj aż kamera będzie gotowa
    if (camera_ready)
    {
        // Wylosuj liczbę i dodaj do odpowiedniego wiaderka
        const uint32_t rnd = generate_random_number();
        sampleCounts[rnd % N_MAX_VALUE]++;
        samplesCount++;

        // Policz rozkład liczb w wiaderkach
        for (int n = 0; n < N_MAX_VALUE; n++)
        {
            if (n > 0) Serial.print(" | ");
            Serial.printf("%.2f", sampleCounts[n] / (float) samplesCount * 100);
            Serial.print("%");
        }

        // Zakończ linię wyświetlając liczbę próbek
        Serial.printf(" | Total: %llu\r\n", samplesCount);
    }
}

Wstępna analiza charakterystyki sensora / generatora

By lepiej filtrować dane losowe z sensora postanowiłem, że podczas uruchamiania programu warto by pobrać trzy zdjęcia w krótkim odstępie czasowym. Pozwala to na łatwą lokalizację danych, które nie są stałe. Opóźnienie jest konieczne, by dać kamerze czas na zmianę buforów kilka-kilkanaście razy, co zapobiega przekłamaniom przy wykrywaniu identycznych wartości.

    // Pobieramy trzy obrazki z kamery co pół sekundy
    for (int n = 0; n < 3; n++)
    {
        camera_fb_t* image = esp_camera_fb_get();
        memcpy(baseFrames + n * FRAME_SIZE, image, FRAME_SIZE);
        esp_camera_fb_return(image);
        delay(500);
    }

Tym samym zmienił się też algorytm wykrywania, który teraz korzysta z funkcji weryfikującej czy dany bajt jest bajtem losowym czy stałym. Funkcja to najprostszy XOR pomiędzy trzema ramkami pobranymi na starcie programu. W celu optymalizacji można policzyć wartości i zwolnić pamięć przypisaną do pobranych ramek, ale to już kwestia implementacyjna.

uint8_t is_frame_data_noisy(const uint32_t index)
{
    // Obliczenie indeksów dla ramek
    const uint32_t realIndex0 = FRAME_SIZE * 0 + index;
    const uint32_t realIndex1 = FRAME_SIZE * 1 + index;
    const uint32_t realIndex2 = FRAME_SIZE * 2 + index;

    // Analiza danych ramek - czy na danym polu wstępuje szum?
    return baseFrames[realIndex0] ^ baseFrames[realIndex1] ^ baseFrames[realIndex2];
}

Nowy algorym generujący

Nowy algorym, podobnie jak poprzedni bazuje na robieniu "zdjęć" kamerą, aczkolwiek dzięki drobnym zmianom używa ramki 96x96px zamiast 240x240, co pozwoliło znacząco zwiększyć wydajność.

// Generuje losową liczbę używając kamery
uint32_t generate_random_number()
{
    // Pobierz bufory z kamery jeżeli nie istnieją
    camera_fb_t* last_buffer = esp_camera_fb_get();

    // Zmienna zawierająca rezultat losowania
    uint32_t result       = 0;
    uint8_t  bit_count = 0;

    // Oblicz losową liczbę uwzględniając cały bufor z oveflowem
    for (uint32_t index = 0; index <= last_buffer->len; index++)
    {
        // Pomiń ramki bez szumu
        if (!is_frame_data_noisy(index)) continue;

        // Pobierz dane z bufora i przypisz do rezultatu
        const uint8_t value = last_buffer->buf[index];
        result = (result << 1) | (value & 0x01);
        bit_count++;

        // Jeżeli mamy całą liczbę zakończ działanie
        if (bit_count == sizeof(uint32_t) * 8) break;
    }

    esp_camera_fb_return(last_buffer); // Zwróć przed-ostatni bufor

    return result;
}

Tym razem algorytm pobiera zdjęcie z ramki i jeżeli dany piksel ramki jest pikselem losowym (patrz porównanie trzech ramek pobranych na starcie programu) to dopisuje ostatni bit koloru danego piksela do wartości losowej (z przesunięciem w lewo). W ten sposób uzyskujemy bardzo duży szum, gdyż LSB (ostatni bit) jest najbardziej podatny na zakłócenia wynikające z tego, że nasz świat i nasze czujniki nie są idealne, a często wystarczy jeden zabłąkany elektron, by zmienić jego wartość.

Gdy uzyskamy pełną wartość (32 bity dla liczby uint32_t) to zamykamy procedurę generacji (early return) i zwracamy bufor do kamery (nikt nie lubi zawieszających się programów), a wygenerowaną liczbę do dalszej obróbki.

Co ciekawe algorym, mimo konstrukcji warunkowej jest nieco szybszy niż poprzednia edycja, a zarazem uzyskuje podobne rezultaty już przy 1-2 tysiącach losowań zamiast 10 tys.

Teraz można uznać to za generator liczb dostatecznie losowych, by im zaufać (nadal nie na tyle, by generować tym kody do głowic atomowych, ale do jakichś bardziej złożonych gier jak najbardziej się nada).