Arytmetyka FIXED POINT - nie mylić z floating point

[virtualny]

Często zachodzi potrzeba wyprowadzenia jakichś danych na zewnątrz, czy to do okna terminala, czy na ekran LCD, czy do pliku... Mierzę częstotliwość, siłą rzeczy wartość nie może być ujemna, ale ponieważ sprintf %d jest dla int, moje "ulepszenia" także będę robił dla "intów", które mogą być ujemne - aby być zgodnym ze standardem sprintf'a().

Mam taki dość mocno odchudzony program, bez HAL,a inicjalizacji zegarów czy portów. Wynik działania programu można oglądać w ST-LINK Utility. Zadanie jest z życia wzięte. A więc w zmiennej i typu int mam wartość częstotliwości w [Hz] 644532. Więc na razie konwertuję sobie do bufora tekstowego liczbę i na ciąg ASCII za pomocą sprintf(). Program jest na bluepillu, działa na wewnętrznym rezonatorze 8MHz - do naszych potrzeb w tej chwili to w zupełności wystarczy.

 

Najpierw żeby było widać użycie RAM zainicjowałem cały RAM gwiazdkami (0x2a) w startupie:

Reset_Handler:
  ldr   r0, =_estack
  mov   sp, r0          /* set stack pointer */
 
    ldr r0, = 0x20000000
    mov r1, 0
    mov r2, 0x2a
filling:
    strb r2, [r0, r1]
    add  r1, r1, #1
    cmp r1, 0x5000
    bne filling
      [...]

Program wygląda tak:

// @file           : main.c

#include <stdint.h>
#include <stdio.h>

__attribute__ ((section(".Var_value"),  used)) int32_t value;          // at 0x20000000
__attribute__ ((section(".Var_length"), used)) uint32_t datalength;    // at 0x20000004

__attribute__ ((section(".outBuffer"), used)) char OUT_BUFFER[32];     // at 0x20000010

int main(void)
{
    int i;

    i = 644532;
    value = i;

    while(1){

        datalength = sprintf(OUT_BUFFER, "%d",  i);

        while(i == value);
        i = value;
    }
}

Kompilacja zajmuje jak poniżej 3052 bajty.

Ważne dla nas zmienne są przypisane do stałych adresów w RAM i łatwo można je podglądać:

Widać ciąg ASCII skonwertowanej zmiennej., zmienną wartości int oraz długości stringu.

 

Teraz zmieniłem nieco program i napisałem procedurę w assemblerze:

    .cpu cortex-m3
    .arch armv7-m
    .fpu softvfp

    .thumb
    .thumb_func
    .syntax unified
    .global my_itoa
    .type   my_itoa, %function


    .text
    .align    2

//========================================================
// DECIMAL CONVERSION OF ANY UNSIGNED VALUE UP TO 32 BIT
//========================================================
       // INPUT:
       //    R0, =  ; POINTER TO OUTPUT char DATA BUFFER
       //    R1, =  ; VALUE TO DECIMAL CONVERT


       // OUTPUT: R0 = LENGTH OF PRODUCED BYTES OF STRING
//========================================================
my_utoa:

        PUSH {R1-R5}  // store registers


        MOV   R5, #0  // LENGTH OF STRING
CALC01:
        //------------------
        //- R4 = R1 DIV 10 -
        //------------------
        LDR   R3, = 0xCCCCCCCD // MAGIC VALUE (!!!)
        UMULL R4,R3,R3,R1      // this three lines looks a bit strange
        LSR   R4,R3, #3        // but here we gotta divide by 10 (seriously!)
        //----------------------------------------------
        MOV   R2, R4         // R2 = R1 div by 10 without the rest
        MOV   R3, #0x0A      // R3 = 10
        MUL   R4, R4, R3     // R4 = R4 * 10

        // mod 10 calculate
        // R4 = R1 mod 10
        SUB   R4, R1, R4     // CALCULATE THE REST r4 = r1 - r4

        ORR   R4, R4, #0x30  // CHANGE TO ASCII NUMBER VALUE "0..9"
        STRB  R4, [R0,R5]    // store next decimal row
        ADD   R5, R5, #1     // R5 = length of string
        MOV   R1, R2         // R1 = before stored value in R2 = (R1 div 10)
        CMP   R1, #0         // R1 = 0? (that was last one operation?)
        BNE   CALC01         // if R1 != 0 then continue CALC01 loop

        // R1 = 0            // R1 = 0, R5 = length of produced string
        STRB  R1, [R0, R5]   // FIRST TIME R1 = 0 SO NULL TERMINATED STRING MAKE NULL
        PUSH  {R5}           // TEMPRARY STORE LENGTH OF STRING
        SUB   R5, R5, #1     // SET OFFSET AT THE END OF STRING (BACKWARD POSSITION)

        // R0 = POINTER TO OUTPUT NULL TERMINATED STRING
        // R5 = OFFSET TO THE END OF STRING (BACKWARD POSSITION)
        // R1 = OFFSET TO THE START OF STRING (FORWARD POSSITION) R1 = 0 AT THE END CALC01 ROUTINE
        // R4 = BACKWARD BYTE (BYTE FROM "RIGHT SIDE")
        // R2 = FORWARD  BYTE (BYTE FROM "LEFT  SIDE")
CALC02:
        LDRB  R4, [R0, R5] // GET DATA FROM THE END (FROM RIGT SIDE)
        LDRB  R2, [R0, R1] // GET DATA FROM THE START (LEFT SIDE)
        STRB  R2, [R0, R5] // GET DATA FROM THE "LEFT  SIDE INTO THE RIGHT SIDE"
        STRB  R4, [R0, R1] // GET DATA FROM THE "RIGHT SIDE INTO THE LEFT  SIDE"
        ADD   R1, R1, #1   // ACTUALIZE STRING FORWARD POSSITION
        SUB   R5, R5, #1   // ACTUALIZE STRING BACKWARD POSSITION
        CMP   R5, R1       // R5 =< R1 ?
        BEQ   END_CALC     // if R5 = R1 go to finish
        BGT   CALC02       // if R5 > R1 continue loop - otherway finish (R5 < R1)

END_CALC:
        // acording declaration this functin is "int" and
        // acordind AAPCS should be returned int value in R0
        // simple "return datalength;" in C
        POP   {R0}         // OUTPUT: R0 = LENGTH OF PRODUCED BYTES OF STRING R0 = R5

        POP {R1-R5}        // restore registers

        BX LR  // ADIOS :)

//=====================================================
//========================================================
// DECIMAL CONVERSION OF ANY UNSIGNED VALUE UP TO 32 BIT
//========================================================
       // INPUT:
       //    R0, =  ; POINTER TO OUTPUT char DATA BUFFER
       //    R1, =  ; VALUE TO DECIMAL CONVERT


       // OUTPUT: R0 = LENGTH OF PRODUCED BYTES OF STRING
//========================================================
my_itoa:
      CMP   R1, 0       // IS OUR VALUE NEGATIVE?
      BGE   my_utoa     // IF IS POSSITIVE GO TO my_sprintf
      PUSH  {LR}        // PC address go back to the main function
      PUSH  {R1}        // save our value for sign print to buffer
      MOV   R1, '-'
      STRB  R1, [R0]    // STORE "-" SIGN AT THE START TEXT BUFFER
      ADD   R0, R0, #1  // MOVE UP 1 BYTE POINTER TO OUTBUFFER
      POP   {R1}
      NEG   R1, R1      // CHANGE VALUE TO POSSITIVE NUMBER
      BL    my_utoa     // CONVERT VALUE TO DECIMAL STRING
      NEG   R1, R1      // RESTORE VALUE TO NEGATIVE NUMBER
                        // now in R0 is datalength from my_sprintf
      ADD   R0, R0, #1  // INCREASSE LENGTH OF STRING MORE 1 BYTE OF SIGN "-"
      POP   {PC}        // GO BACK TO THE MAIN FUNCTION
//======================================================

 

Plik main.c wygląda tak:

// @file           : main.c

#include <stdint.h>
#include <stdio.h>

extern int my_itoa(char* out_buff, int32_t num);

__attribute__ ((section(".Var_value"),  used)) int32_t value;          // at 0x20000000
__attribute__ ((section(".Var_length"), used)) uint32_t datalength;    // at 0x20000004

__attribute__ ((section(".outBuffer"), used)) char OUT_BUFFER[32];     // at 0x20000010

int main(void)
{
    int i;
    i = 644532;
    value = i;

    while(1){

//        datalength = sprintf(OUT_BUFFER, "%d",  i);
        datalength = my_itoa(OUT_BUFFER,  i);
        while(i == value);
        i = value;
    }
}

 

Kompilacja w tej wersji zajęła 692 bajty

wynik działania jest taki sam

 

Teraz małe doświadczenie.

dopisuję 2 linie przed pętlą while:

    float y;
    y = i;

I po kompilacji program zajmuje ponad 1200 bajtów

Dopisuję jeszcze jedną linię:

    y = y/999.9;

I program zajmuje po kompilacji już ponad 3000 bajtów:

Idźmy dalej - chciałbym częstotliwość w [Hz] wyrazić w [kHz] więc zamieniam linię wywołującą my_itoa() na:

datalength = sprintf(OUT_BUFFER, "%.3f",  y);

 

I program zajmuje już ponad 5600 bajtów - ale to nie wszystko w podglądzie jeszcze nie pojawia się string, i otrzymuję błąd, że muszę ustawić taką właściwość:

I teraz program po kompilacji zajmuje ponad 17000 bajtów, za to już działa poprawnie i widać string wyprowadzony w [kHz]:

pojawiła się w stringu kropka na właściwej pozycji, i długość stringu zmieniła się z 6 na 7 znaków:

 

Funkcja main wygląda tak:

int main(void)
{
    int i;
    i = 644532;
    value = i;
    float y;

    while(1){
        y = i;
        y = y/1000;
        datalength = sprintf(OUT_BUFFER, "%.3f",  y);
        while(i == value);
        i = value;
    }
}

 

To uzyskaliśmy korzystając z usług matematyki zmiennoprzecinkowej (floatingpoint)

 

 

 

 

Edytowano Lipiec 13, 2023 przez virtualny

[virtualny]

FIXED POINT ISSUE#2

Teraz należałoby się zastanowić tak "bardzowysoko poziomowo", (tak jak ludzie od C++ albo jeszcze "wyżej") co tak naprawdę końcowy program zrobił. Odłóżmy na bok rozważania o floating point IEEExxxx, małych indianach, dużych indianach, mantysach, normalizacjach czy tego co bajt po bajcie wykonywał procesor bo utoniemy.

Spójrzmy na ogólne działanie programu CO ON TAKIEGO ZROBIŁ?

Albo jeszcze inaczej - CO MUSIMY ZROBIĆ, ŻEBY POWTÓRZYĆ WYNIK DZIAŁANIA PROGRAMU FLOATING POINT?

tak naprawdę potrzebujemy zrobić 2 rzeczy:

1. Skonwertować liczbę binarną do stringu ASCII NULL terminated

2. Przesunąć o "1 bajt w prawo" część stringu, a w miejscu "rozsunięcia" wstawić kropkę

 

Oto wynik wysokopoziomego rozważania - czy trudno zrobić te dwie rzeczy? Liczbę już do stringu konwertowaliśmy, co do drugiego punktu napisałem w C (!!!) taką procedurę:

int Make_Fixed_Point(char * OUT_BUFF, uint32_t datalen, uint32_t fix ){
    uint32_t i;
    fix ++; // need rewrite WITH a NULL terminated to the "right side"
    if(datalen == 1){
        OUT_BUFF[2] = OUT_BUFF[0];
        OUT_BUFF[0] = 0x30;
        OUT_BUFF[1] = '.';
        OUT_BUFF[3] = 0; // null terminated string
        datalength=3; // "(0.x)"
        return 1;
    }
    for(i=0; i<fix;i++){
        OUT_BUFF[(datalen+1)-i] = OUT_BUFF[datalen -i];
    }
    OUT_BUFF[(datalen+1)-i]  = '.'; // fix the point :-)
    datalength ++; // added dot ('.') to the string and it is longer 1 byte more

    return 0;
}

Analizę procedury pozostawiam dociekliwym.

 

Nasz program zawiera się w pliku main.c i w pliku assemblera (funkcja my_itoa())  my_sprintf.s

my_sprintf.s wygląda następująco:

    .cpu cortex-m3
    .arch armv7-m
    .fpu softvfp

    .thumb
    .thumb_func
    .syntax unified
    .global my_itoa
    .type   my_itoa, %function
    .type   my_utoa, %function

    .text
    .align    2

//========================================================
// DECIMAL CONVERSION OF ANY UNSIGNED VALUE UP TO 32 BIT
//========================================================
       // INPUT:
       //    R0, =  ; POINTER TO OUTPUT char DATA BUFFER
       //    R1, =  ; VALUE TO DECIMAL CONVERT


       // OUTPUT: R0 = LENGTH OF PRODUCED BYTES OF STRING
//========================================================
my_itoa:
      CMP   R1, 0       // IS OUR VALUE NEGATIVE?
      BGE   my_utoa     // IF IS POSSITIVE GO TO my_sprintf
      PUSH  {LR}        // PC address go back to the main function
      PUSH  {R1}        // save our value for sign print to buffer
      MOV   R1, '-'
      STRB  R1, [R0]    // STORE "-" SIGN AT THE START TEXT BUFFER
      ADD   R0, R0, #1  // MOVE UP 1 BYTE POINTER TO OUTBUFFER
      POP   {R1}
      NEG   R1, R1      // CHANGE VALUE TO POSSITIVE NUMBER
      BL    my_utoa     // CONVERT VALUE TO DECIMAL STRING
      NEG   R1, R1      // RESTORE VALUE TO NEGATIVE NUMBER
                        // now in R0 is datalength from my_sprintf
      ADD   R0, R0, #1  // INCREASSE LENGTH OF STRING MORE 1 BYTE OF SIGN "-"
      POP   {PC}        // GO BACK TO THE MAIN FUNCTION
//======================================================

//========================================================
// DECIMAL CONVERSION OF ANY UNSIGNED VALUE UP TO 32 BIT
//========================================================
       // INPUT:
       //    R0, =  ; POINTER TO OUTPUT char DATA BUFFER
       //    R1, =  ; VALUE TO DECIMAL CONVERT


       // OUTPUT: R0 = LENGTH OF PRODUCED BYTES OF STRING
//========================================================
my_utoa:

        PUSH {R1-R5}  // store registers


        MOV   R5, #0  // LENGTH OF STRING
CALC01:
        //------------------
        //- R4 = R1 DIV 10 -
        //------------------
        LDR   R3, = 0xCCCCCCCD // MAGIC VALUE (!!!)
        UMULL R4,R3,R3,R1      // this three lines looks a bit strange
        LSR   R4,R3, #3        // but here we gotta divide by 10 (seriously!)
        //----------------------------------------------
        MOV   R2, R4         // R2 = R1 div by 10 without the rest
        MOV   R3, #0x0A      // R3 = 10
        MUL   R4, R4, R3     // R4 = R4 * 10

        // mod 10 calculate
        // R4 = R1 mod 10
        SUB   R4, R1, R4     // CALCULATE THE REST r4 = r1 - r4

        ORR   R4, R4, #0x30  // CHANGE TO ASCII NUMBER VALUE "0..9"
        STRB  R4, [R0,R5]    // store next decimal row
        ADD   R5, R5, #1     // R5 = length of string
        MOV   R1, R2         // R1 = before stored value in R2 = (R1 div 10)
        CMP   R1, #0         // R1 = 0? (that was last one operation?)
        BNE   CALC01         // if R1 != 0 then continue CALC01 loop

        // R1 = 0            // R1 = 0, R5 = length of produced string
        STRB  R1, [R0, R5]   // FIRST TIME R1 = 0 SO NULL TERMINATED STRING MAKE NULL
        PUSH  {R5}           // TEMPRARY STORE LENGTH OF STRING
        SUB   R5, R5, #1     // SET OFFSET AT THE END OF STRING (BACKWARD POSSITION)

        // R0 = POINTER TO OUTPUT NULL TERMINATED STRING
        // R5 = OFFSET TO THE END OF STRING (BACKWARD POSSITION)
        // R1 = OFFSET TO THE START OF STRING (FORWARD POSSITION) R1 = 0 AT THE END CALC01 ROUTINE
        // R4 = BACKWARD BYTE (BYTE FROM "RIGHT SIDE")
        // R2 = FORWARD  BYTE (BYTE FROM "LEFT  SIDE")
CALC02:
        LDRB  R4, [R0, R5] // GET DATA FROM THE END (FROM RIGT SIDE)
        LDRB  R2, [R0, R1] // GET DATA FROM THE START (LEFT SIDE)
        STRB  R2, [R0, R5] // GET DATA FROM THE "LEFT  SIDE INTO THE RIGHT SIDE"
        STRB  R4, [R0, R1] // GET DATA FROM THE "RIGHT SIDE INTO THE LEFT  SIDE"
        ADD   R1, R1, #1   // ACTUALIZE STRING FORWARD POSSITION
        SUB   R5, R5, #1   // ACTUALIZE STRING BACKWARD POSSITION
        CMP   R5, R1       // R5 =< R1 ?
        BEQ   END_CALC     // if R5 = R1 go to finish
        BGT   CALC02       // if R5 > R1 continue loop - otherway finish (R5 < R1)

END_CALC:
        // acording declaration this functin is "int" and
        // acordind AAPCS should be returned int value in R0
        // simple "return datalength;" in C
        POP   {R0}         // OUTPUT: R0 = LENGTH OF PRODUCED BYTES OF STRING R0 = R5

        POP {R1-R5}        // restore registers

        BX LR  // ADIOS :)

//=====================================================

I nasz main.c:

// @file           : main.c

#include <stdint.h>


extern int my_itoa(char* out_buff, int32_t num);

__attribute__ ((section(".Var_value"),  used)) int32_t value;          // at 0x20000000
__attribute__ ((section(".Var_length"), used)) uint32_t datalength;    // at 0x20000004

__attribute__ ((section(".outBuffer"), used)) char OUT_BUFFER[32];     // at 0x20000010
//-------------
int Make_Fixed_Point(char * OUT_BUFF, uint32_t datalen, uint32_t fix );
//-------------

//-------------------------------------------------------------------------------------------
int main(void)
{
    int i;
    i = -777888;
    value = i;

    while(1){
        datalength = my_itoa((char*)&OUT_BUFFER,  i);
        if(i < 0){
            Make_Fixed_Point((char*) &OUT_BUFFER[1], datalength-1, 3);
        } else {
            Make_Fixed_Point((char*) &OUT_BUFFER[0],datalength, 3);
        }
        while(i == value);
        i = value;
    }
}
//--------------------------
int Make_Fixed_Point(char * OUT_BUFF, uint32_t datalen, uint32_t fix ){
    uint32_t i;
    fix ++; // need rewrite WITH a NULL terminated to the "right side"
    if(datalen == 1){
        OUT_BUFF[2] = OUT_BUFF[0];
        OUT_BUFF[0] = 0x30;
        OUT_BUFF[1] = '.';
        OUT_BUFF[3] = 0; // null terminated string
        datalength=3; // "(0.x)"
        return 1;
    }
    for(i=0; i<fix;i++){
        OUT_BUFF[(datalen+1)-i] = OUT_BUFF[datalen -i];
    }
    OUT_BUFF[(datalen+1)-i]  = '.'; // fix the point :-)
    datalength ++; // added dot ('.') to the string and it is longer 1 byte more

    return 0;
}
//-----------------------------------------------------------------------------------

Plik po kompilacji zajmuje 892 bajty, z czego blisko połowa to i tak narzut kompilatora, który dołącza rzeczy które on uważa za konieczne, co w naszym przypadku jest zbędne. Ale OK nie będę przeprowadzał inwestygacji gdzie i jak "odchudzić" i tak już ponad 17 razy odchudzony program - przypominam że wersja z floatami miała ponad 17000 bajtów. 

Poniżej wynik działania programu w ST-LINK Utility:

Program zrobił w końcowym efekcie to samo, co jego "floatingpointowy" odpowiednik.

 

Nie jest to może całe zagadnienie aka ARYTMETYKA FIXED POINT, ale jest to dobry wstęp do tej arytmetyki.

Nasz program sFIXował naszego "pointa" we właściwe miejsce.

 

W załącznikach binka do flaszowania bluepilla oraz cały program. 

 

 

 

 

BIN_C_MIXED_ASM.zip C_MIXED_ASM.ZIP

Edytowano Lipiec 13, 2023 przez virtualny

[virtualny]

Do tej pory to co zrobiliśmy „fixedpointowo” zrobiliśmy na integerach i tak naprawdę właśnie na tym polega arytmetyka FIXED POINT.

Teraz zastanówmy się czy da się na integerach wyrazić takie działanie jak 1/4?

Czyli w liczniku mamy 1, w mianowniku 4, więc niby się nie da ALE… W całej arytmetyce FIXED POINT może ciut podobnie jak we floating point wszystko polega NA ODPOWIEDNIM SKALOWANIU LICZBY...  W przypadku FIX-ed point na ODPOWIEDNIM SKALOWANIU LICZBY W LICZNIKU, ABY BYŁA ODPOWIEDNIO WIĘKSZA, o dekadę, czy nawet rzędy dekad od mianownika – wtedy zawsze matematyka nam zadziała.

 

Proste ćwiczenie:

1/4  się nie da ALE przykładowo:

 

1*100/4 JUŻ SIĘ DA!

- musimy pamiętać, że licznik przeskalowaliśmy w górę o 2 dekady

I teraz:

100 / 4 = 25

Pamiętając że wynik mamy przeskalowany o 2 dekady „FIX-ujemy” naszego pointa w lewo o 2 miejsca od końca stringu wyniku (od prawej strony przesuwamy w lewo) czyli z naszego

25 robi się

.25

Chociaż zapis „.25” jest poprawny, to dla zwiększenia czytelności zrobimy dodatkową sztuczkę. Mianowicie cały string „.25” przesuniemy w prawo o 1 miejsce i na początku stringu wstawimy „0”, co w końcowym efekcie da nam:

 

0.25

Czyli działając TYLKO NA INTEGERACH potrafimy przedstawiać ułamki zabawiając się stringiem, czyli FIX-ując pointa.

Jeszcze tylko dla przykładu jeżeli nasz licznik przeskalujemy o 3 dekady matematyka nadal zadziała:

1*1000 / 4 =

250 – tym razem FIX-ujemy pointa o 3 dekady w lewo, co nam daje

= .250 =

= 0.250 lub jak ktoś woli

0.25 (!!!)

Spójrzmy teraz na działanie z życia wzięte:

 

Patrząc na równanie można wydzielić tu stałą i pomnożyć ją przez odpowiednią ilość dekad (20 !!!), aby uzyskać wynik powyżej jedności, aby działania były prawidłowe.

 

Mamy tutaj 1/4PI^2, więc przeskalowujemy nasz licznik o 20 dekad i dzielimy go przez (4*Pi^2) co daje taką magiczną liczbę:

100 000 000 000 000 000 000/4/Pi/Pi = 2 533 029 591 058 444 286

 

Kończąc działanie musimy podzielić naszą magiczną liczbę  przez ((F1^2)*(Cown)), co można zapisać jako ciąg dzieleń:

Lown = Magic_nr/F1/F1/Cown

Arytmetyka doszła do integerów 64 bitowych, ale daje radę. Otrzymany wynik jest w dziesiątkach nanohenrów, więc aby go przedstawić w mikrohenrach należałoby sFIX-ować naszego pointa w lewo o 2 miejsca. Mogę zapewnić, że działa to znakomicie, szczególnie zainteresowani tym powinni być użytkownicy 8bitowców.

W C tak wygląda to obliczenie:

uint64_t magic_value = 2533029591058444286;

static uint32_t f1_base = 644060; [Hz]
static uint32_t c_own = 1030;  [pF]
static uint32_t l_own = 5928; // [uH * 100] so = 59.28 [uH]

l_own = magic_value/f1_base/f1_base/c_own;

 

No i tak wygląda arytmetyka FIXED POINT.