espressif / esp-dsp

DSP library for ESP-IDF

Espressif DSP Library

ESP-DSP is the official DSP library for all Espressif chips. The library contains optimized functions for ESP32 and ESP32-S3 chips.

Overview

ESP-DSP is intended to be used as an ESP-IDF component. For the introduction to ESP-IDF, refer to the ESP-IDF Programming Guide.

The ESP-DSP library includes implementations of the following functions:

• Matrix multiplication: reference
• Dot product: reference, example
• FFT: reference, example
• IIR: reference, example
• FIR: reference
• Vector math operations: reference
• Kalman filter: reference

Many of the library functions are written in assembly and are optimized for the CPU configuration used in the ESP32. In addition to the optimized implementations, reference implementations written in ANSI C are provided.

Function implementations are provided for single precision floating point (32-bit float), and 16-bit signed integers.

Documentation

• ESP-DSP Overview
• ESP-DSP API Reference
• ESP-DSP Benchmarks

Documentation found in the above links is automatically generated from the contents of this repository. If you find that some information is missing or incomplete, please report an issue.

Installation and Usage

The ESP-DSP library is a component for the ESP-IDF build system.

The recommended way to use the component is to install it from the IDF Component Registry.

Adding ESP-DSP component to an existing project

In the project directory, run:

idf.py add-dependency "espressif/esp-dsp"

This will add the esp-dsp component as a dependency to the main component of your project. You can also add it by editing the idf_component.yml file manually.

Downloading ESP-DSP examples

You can download the example projects from the IDF Component Registry website or use the idf.py create-project-from-example command. For example:

idf.py create-project-from-example "espressif/esp-dsp:basic_math"

Please refer to the IDF Component Registry for the download links and the instructions.

You can also use Git to clone this repository and find all the examples in the examples/ subdirectory. For the list of the examples, please see README.md in the examples directory.

Building and running ESP-DSP examples

Build, flash and monitor as this is usually done for ESP-IDF projects:

idf.py -p PORT flash monitor

where PORT is the UART port name of your development board, such as /dev/ttyUSB0 or COM1.

Note that you need to set up ESP-IDF before building the project. Refer to the ESP-IDF Getting Started Guide if you don't have the environment set up yet.

Reporting Issues

If you have found an issue in ESP-DSP, or wish to submit an enhancement request, please use the Issues section on Github.

For general questions related to this library, please use the esp32.com forum.

Contributing to ESP-DSP

Please check CONTRIBUTING.md if you'd like to contribute to ESP-DSP.

Copyrights and License

All original source code in this repository is Copyright (C) 2018-2023 Espressif Systems. This source code is licensed under the Apache License 2.0 as described in the file LICENSE.

esp-dsp's Issues

Two potential issues regarding dsps_fft4real example as well as documentation for cplx2real(). (DSP-91)

Hello. I have found two potential issues while working with esp-dsp. These issues are unrelated to each other.

1. In the dsps_fft4real example. When the result of cplx2real() is converted from complex to real power values, a division of N is used (aka binsize*2) However I would argue that a division of (binsize)^2 should be used instead when converting to power.
   Pow = ampl^2 --> Pow = (sqrt(Real^2+Img^2)/binsize)^2 --> Pow = (Real^2+Img^2) / binsize^2
   So the scaling in the dsps_fft4real example should be (N/2)^2 instead correct?

2. In the documentation for dsps_cplx2real_sc16_ansi() it is stated that "Convert FFT result of complex FFT for real input to real array". However, as far as I understand, the result of cplx2real() is not real but complex. In the dsps_fft4real example the output of cplx2real() is also used as if it was complex. I understand that cplx2real has to be used when 1 real sequence is used as input, but is it not misleading to state that the output of cplx2real() is real?

Explain FFT example (DSP-69)

Hi, I am looking to do FFT on a signal coming from the accelerometer.
I ahve 512 sample readings and I know the frequency. I used FFTW library in python to do the FFT for the signal and it's working.
How can I use this library to get the same thing? I had a look over your example, but I don't understand exactly what x1 and x2 are and how I should modify it.

Regards,
Gabriel

inverse FFT

Feature request:

Ability to make an inverse FFT with this library.

Br
Stephan

Resampler in esp-dsp, feature request (DSP-90)

Hi,
There are many occasions where a resampler is needed without having the complete esp-adf framework.
Specially since esp-adf is relying in many tweaks and specific versions or git checkouts that makes it almost impossible to properly use it or even try to follow its own intricacies. All these make it a really difficult environment to use.
A very handy function that everybody in DSP needs is the resampler but unfortunately it is inside esp-adf..

In my view, resampler belongs better in the esp-dsp, whereas almost all such DSP libraries got a resample function as this is the norm.
Please consider to add it in the esp-dsp since the esp-dsp can be actually used with almost all esp-idf versions, even the master/development.

Please update the esp-dsp on the package manager (DSP-96)

The esp-dsp on the package manager is not the latest esp-dsp, and it does not compile on the idf.py master

Compilation error in fft4real example for ANSI DSP optimization configuration.

I tested fft4real example for ANSI DSP optimization but got below compile error.

Error:
C:/esp-dsp/modules/fft/include/dsps_fft4r.h:157:29: error: implicit declaration of function 'dsps_bit_rev4r_fc32_ansi'; did you mean 'dsps_bit_rev_fc32_ansi'? [-Werror=implicit-function-declaration]

如何使用xTaskCreatePinnedToCore函数来加快esp32的运算速度 (DSP-67)

Hi:
我现在使用esp32进行图像处理，使用xTaskCreatePinnedToCore( imageprocess, " imageprocess", 1024*10, NULL, 10, NULL, 0 ) 来设定图像处理函数指向0核。但是发现使用这个函数把任务指向0核和1核，两者的运算速度并没有提升很多。请问一下这是什么原因？使用的是C语言。谢谢！

Add autocorrelation and cross-correlation functions (DSP-116)

Very useful for DSP

Feature request: Optimized FIR with int32_t (DSP-68)

Hi,

Would be great if you could make an optimized FIR filter for int32_t.

Best Regards
Patrik Berglund

modules/math/sqrt/float/dsps_sqrt_f2_ansi.c build error (DSP-89)

Environment

• Development Kit: ESP32-S3-DevKitC
• IDF version: v5.0-dev-4303-g075e0729de
• Build System: CMake
• Compiler version: xtensa-esp32-elf-gcc (crosstool-NG esp-2022r1-RC1) 11.2.0
• Operating System: macOS
• Power Supply: USB

Problem Description

Build doesn't error if build with compiler debug mode, but when build with compiler optimization 'Optimize for performance (-O2)' get build error as below.

Should it be as follows to return a float instead of a pointer to a float?

inline float dsps_sqrtf_f32_ansi(float f)
{
    int* f_ptr = (int*)&f;
    const int result = 0x1fbb4000 + (*f_ptr >> 1);
    float* f_result = (float*)&result;
    return f_result;   
}

Debug Logs

/Users/davidmann/w/Haikubox2-firmware/modules/math/sqrt/float/dsps_sqrt_f32_ansi.c:24:12: error: 'result' is used uninitialized [-Werror=uninitialized]
   24 |     return *f_result;
      |            ^~~~~~~~~
/Users/davidmann/w/Haikubox2-firmware/modules/math/sqrt/float/dsps_sqrt_f32_ansi.c:22:15: note: 'result' declared here
   22 |     const int result = 0x1fbb4000 + (*f_ptr >> 1);

建议增加半带滤波器函数

----------------------------- Delete below -----------------------------

If your issue is a general question, starts similar to "How do I..", or is related to 3rd party development kits/libs, please discuss this on our community forum at esp32.com instead.

INSTRUCTIONS

Before submitting a new issue, please follow the checklist and try to find the answer.

• I have read the documentation ESP-IDF Programming Guide and the issue is not addressed there.
• I have updated my IDF branch (master or release) to the latest version and checked that the issue is present there.
• I have searched the issue tracker for a similar issue and not found a similar issue.

If the issue cannot be solved after the steps before, please follow these instructions so we can get the needed information to help you in a quick and effective fashion.

1. Fill in all the fields under Environment marked with [ ] by picking the correct option for you in each case and deleting the others.
2. Describe your problem.
3. Include debug logs on the monitor or the coredump.
4. Provide more items under Other items if possible can help us better locate your problem.
5. Use markup (buttons above) and the Preview tab to check what the issue will look like.
6. Delete these instructions from the above to the below marker lines before submitting this issue.

----------------------------- Delete above -----------------------------

Environment

• Development Kit: [ESP32-Wrover-Kit|ESP32-DevKitC|ESP32-PICO-Kit|ESP32-LyraT|ESP32-LyraTD-MSC|none]
• Kit version (for WroverKit/PicoKit/DevKitC): [v1|v2|v3|v4]
• Module or chip used: [ESP32-WROOM-32|ESP32-WROOM-32D|ESP32-WROOM-32U|ESP32-WROVER|ESP32-WROVER-I|ESP32-WROVER-B|ESP32-WROVER-IB|ESP32-SOLO-1|ESP32-PICO-D4|ESP32]
• IDF version (run git describe --tags to find it):
  // v3.2-dev-1148-g96cd3b75c
• Build System: [Make|CMake]
• Compiler version (run xtensa-esp32-elf-gcc --version to find it):
  // 1.22.0-80-g6c4433a
• Operating System: [Windows|Linux|macOS]
• Power Supply: [USB|external 5V|external 3.3V|Battery]

Problem Description

//Detailed problem description goes here.

Expected Behavior

Actual Behavior

Steps to repropduce

1. step1
2. ...

// It helps if you attach a picture of your setup/wiring here.

Code to reproduce this issue

// the code should be wrapped in the ```cpp tag so that it will be displayed better.
#include "esp_log.h"

void app_main()
{
    
}

// If your code is longer than 30 lines, GIST is preferred.

Debug Logs

Debug log goes here, should contain the backtrace, as well as the reset source if it is a crash.
Please copy the plain text here for us to search the error log. Or attach the complete logs but leave the main part here if the log is *too* long.

Other items if possible

• sdkconfig file (attach the sdkconfig file from your project folder)
• elf file in the build folder (note this may contain all the code details and symbols of your project.)
• coredump (This provides stacks of tasks.)

Memory alignment issues (DSP-80)

There are some places in this library where the user must align memory passed to functions correctly. These are not documented anywhere I can find.

E.G. The dsps_fft4r_fc32_ansi_ function casts the float *data parameter to the following struct:

typedef union fc32_u
{
    struct
    {
        float re;
        float im;
    };
    uint64_t data;
}fc32_t;

The uint64_t member of this union requires 8 bytes alignment. Actually, this member is unused, so it would be best to remove it, and make the default 4 byte alignment work. Why doesn't this library use the C99 complex type feature?

I've also noticed that 16 byte alignment was added to a lot of the example apps with the support for ESP32S3 chip in 108493c. Is this alignment only required for implementations using assembly code for that chip?

esp-dsp/modules/common/include/dsp_tests.h

Line 34 in 3175e82

#define memalign(align_, size_) malloc(size_)

The tests disable alignment on esp-idf version <4.3.0 by defining memalign as malloc and ignoring the alignment parameter. Would this not cause issues when loading memory from an unaligned address?

ESP32-S2 support?

Hello. Will you add ESP32-S2 support for ESP-DSP?

Is dsps_fir_f32_aes3 implementation working? (DSP-92)

Hi,

Trying to utilize FIR on a ESP32S3 (ESP32-S3-DevKitC-1) and seen the esp-dsp FIR implementation file here
https://github.com/espressif/esp-dsp/blob/master/modules/fir/float/dsps_fir_f32_aes3.S

Tried a test of my own (based on test_app) and its functionality show FAIL whereas its result is different from the standard ansi result.

Is there any example/test that we can do for ESP32S3 on esp-dsp FIR?
Is this implementation file working correctly?

Regards,

/Edit
Also seen this issue, but do not know its status
#44 (comment)

could you add support for basic fast sin-cos function set to speed-up math calc (DSP-88)

INSTRUCTIONS

The default sin-cos functions will cause math iterate compute, which is so slow and unsuitable for a MCU, many platform use lookup table and IQmath format to speed-up those math functions on MCU, especially MCUs without FPU.

Fixed-point FFT is slower than floating point FFT

Hi,
Is there any official benchmarks for the speed of fixed point FFTs?https://docs.espressif.com/projects/esp-dsp/en/latest/esp-dsp-benchmarks.html does not seem to be updated.

I've been testing myself on a AI-Thinker ESP32-CAM board, and my results for N=64 show that the sc16 FFT is slower than fc32 FFT by about 40%. This hold true for N=1024 as well, where it was 130k cycles for floating point, and 230k cycles for fixed point. Is that expected performance or did I do something wrong?

建议增加更多的矩阵运算函数 (DSP-84)

在你们的esp-drone开源项目中用到的矩阵求逆和矩阵转置函数都是从arm的dsp库移植过来的，然而在你们的官方的dsp库没有这两个功能函数，非常希望用到你们官方自己出的矩阵运算函数。

BLAS and LAPACK on ESP32

I'm curious if XTensa has an optimized BLAS library for their processors which could be used on ESP32? It sounds like the assembly code in this repo that are optimized for vector / matrix operations might be able to be used for that purpose? It doesn't look like OpenBLAS supports the XTensa processor.

Assuming the "model implementation" Fortran 77 version of BLAS works on the ESP32, I'd be interested in using LAPACKE on ESP32 and seeing the performance comparisons. Has anyone tried using LAPACK on ESP32?

Thanks!

Support for more image processing functions (DSP-81)

It would be great if there was support for some image processing operations like:

1. Alpha blending (a bit like: out = x * alpha + y * (1 - alpha))
2. Conversion from/to difference colorspace (RGB888 <=> RGB565)
3. Optimized blitting (copying some memory area to some other memory area, maybe using the new DMA engine in ESP32 S3)
4. Texture mapping ( out = bilinear(img, [x,y]) with x,y in |R not |N)
5. etc...

Many LCD library have to deal with RGB565 format, and constantly changing from masked u16 (red = c & 0xF800 >> 8, etc...) to i16 for operations and back to u16 is very costly in terms of performance. There might be improvement to get here when using primitives from Xtensa (like MAC16, maybe).

Error in FIR benchmark tests (DSP-74)

Should this line reference fir2 instead of fir1?

esp-dsp/test/test_dsp.c

Line 110 in 1009c9d

&fir1, data1, data2, 1024);

Compiled as in the repo, I get these numbers from the overall benchmark (ie, test '2'):

| **FIR Filters**                                          |          |          |
+----------------------------------------------------------+----------+----------+
| dsps_fir_f32 1024 input samples and 256 coefficients     |  1339099 |  5147987 |
+----------------------------------------------------------+----------+----------+
| dsps_fird_f32 1024 samples, 256 coeffs and decimation 4  |    19495 |    36495 |

In the Espressif docs, I see the decimating FIR numbers are about 2x higher: https://docs.espressif.com/projects/esp-dsp/en/latest/esp-dsp-benchmarks.html

I think that fir1.decim is uninitialised, so the results aren't stable. I've gotten different results when recompiling, without changing anything significant.

Changing that reference to fir2 gives me:

| **FIR Filters**                                          |          |          |
+----------------------------------------------------------+----------+----------+
| dsps_fir_f32 1024 input samples and 256 coefficients     |  1339102 |  5147994 |
+----------------------------------------------------------+----------+----------+
| dsps_fird_f32 1024 samples, 256 coeffs and decimation 4  |   350247 |  1317839 |

These numbers are now 9x and 16x higher than in the Espressif docs, but are about what I would expect - decimating by 4 requires about 4x less CPU time.

Zero overhead loops in esp-dsp

• Development Kit: all ESP32
• IDF version : master
• Compiler version : 8.4 2021r2

Problem Description

This part of esp-idf suggests that there is a sporadic? (or just rare?) issue with zero overhead loops:
https://github.com/espressif/esp-idf/blob/master/components/xtensa/esp32/include/xtensa/config/core.h#L1405
That's why it's usage is turned off in gcc.

Now esp-dsp does use these loops (seemingly without issues). Can you provide us with some details in the topic? I found no further info on this erratum 572.

Thanks
Viktor

How do I run the test suite?

I tried to compile and run the "test_app" included here, however it just says:

Here's the test menu, pick your combo:

Enter test for running.

I enter a number, and get:

-----------------------
0 Tests 0 Failures 0 Ignored
OK
Enter next test, or 'enter' to see menu

I guess that the files in the test_app folder don't like up with the test suite correctly, how do I make it work?

Meaning of divide by N (DSP-94)

Hello

I have 2 question on the next formule:

y2_cf[i] = ((y_cf[i * 2 + 0] * y_cf[i * 2 + 0] + y_cf[i * 2 + 1] * y_cf[i * 2 + 1])/N);

What is the meaning of devide by N in above formule.

Why is there not sqrt() function ?

Thanks

dsps_cplx2real_fc32 cannot be used without fft4r initialization (DSP-73)

In my application I'm using radix-2 FFT (I'm using 4096 real points so FFT is 2048 points).
Current implementation of dsps_cplx2real_fc32 requires fft radix-4 to be initialized to work properly.

Why there is no implementation for radix-2 alone? Having to init radix-4 wastes 32kB of RAM in my application for tables that are only needed for dsps_cplx2real_fc32.

Matrix subtraction does not work correctly

Hi.

I found a serious problem on matrix subtraction.
The subtraction function returns the opposite sign matrix.
In other words, when you calculate A - B, the function returns B - A.

Please try this code replacing the matrix example here.

In addition, I try this code on M5Stack Fire.

How could we fix this problem?

建议增加半带滤波器 (DSP-82)

可以使用半带滤波器加抽取减小运算量

FFT example does not generate proper results with IDF V5.0 Master

Environment

• Development Kit: ESP32-S3-DEVKITC N8R8
• Kit version DevKitC
• Module or chip used: ESP32-S3-WROOM1
• IDF version: v5.0-dev-4303-g075e0729de
• Build System: CMake
• Compiler version: xtensa-esp32-elf-gcc (crosstool-NG esp-2022r1-RC1) 11.2.0
• Operating System: macOS
• Power Supply: USB

Problem Description

FFT example builds and runs on ESP32-S3 using latest V5 IDF, but it generates erroneous output. No changes were made to this example: https://github.com/espressif/esp-dsp/tree/master/examples/fft

Expected Behavior

Plots like shown in readme with single or double peak.

I (59) main: Start Example.
W (89) main: Signal x1
I (89) view: Data min[495] = -162.760925, Data max[164] = 23.938747
 ________________________________________________________________
0                                                                |
1                    |                                           |
2                    |                                           |
3                    |                                           |
4                    |                                           |
5                    |                                           |
6                   | |                                          |
7                   | |                                          |
8                  || ||                                         |
9||||||||||||||||||     ||||||||||||||||||||||||||||||||||||||||||
 0123456789012345678901234567890123456789012345678901234567890123
I (159) view: Plot: Length=512, min=-60.000000, max=40.000000
W (169) main: Signal x2
I (169) view: Data min[502] = -164.545135, Data max[205] = 3.857752
 ________________________________________________________________
0                                                                |
1                                                                |
2                                                                |
3                         |                                      |
4                         |                                      |
5                         |                                      |
6                         |                                      |
7                         ||                                     |
8                        | |                                     |
9||||||||||||||||||||||||   ||||||||||||||||||||||||||||||||||||||
 0123456789012345678901234567890123456789012345678901234567890123
I (249) view: Plot: Length=512, min=-60.000000, max=40.000000
W (249) main: Signals x1 and x2 on one plot
I (259) view: Data min[505] = -159.215271, Data max[164] = 23.938747
 ________________________________________________________________
0                                                                |
1                    |                                           |
2                    |                                           |
3                    |    |                                      |
4                    |    |                                      |
5                    |    |                                      |
6                   | |   |                                      |
7                   | |   ||                                     |
8                  || || | |                                     |
9||||||||||||||||||     |   ||||||||||||||||||||||||||||||||||||||
 0123456789012345678901234567890123456789012345678901234567890123
I (339) view: Plot: Length=512, min=-60.000000, max=40.000000
I (339) main: FFT for 1024 complex points take 140472 cycles
I (349) main: End Example.

Actual Behavior

W (349) main: Signal x1
I (349) view: Data min[151] = -40.703781, Data max[1] = 10.201058
 ________________________________________________________________
0                                                                |
1                                                                |
2| |                                                          | ||
3| |||   | |||| || ||||||||| ||||  | || | || || ||   |||||   |||||
4||||||||||||||||||||||||||||||||||||||||||||||||| ||||||||||||| |
5 |  |||||| | ||| |||  ||   |   |||||| ||| || ||| ||| |||||||    |
6 |                |        |     |      |        |||            |
7                                                                |
8                                                                |
9                                                                |
 0123456789012345678901234567890123456789012345678901234567890123
I (419) view: Plot: Length=512, min=-60.000000, max=40.000000
W (429) main: Signal x2
I (429) view: Data min[272] = -52.645767, Data max[1] = 10.407180
 ________________________________________________________________
0                                                                |
1                                                                |
2| |                                                          | ||
3| |||   | ||||||| ||||||||  |||| |  |||||||  | |    |||||   |||||
4||||| ||| ||||||||||||||||||||||||||||||||||||||| ||||||||||||| |
5 | ||||| ||| |||||     |  |    || ||  | |   |||||||| | |||||    |
6 |   ||       |  |                |   |       |  ||        |    |
7              |                   |                        |    |
8                                  |                             |
9                                                                |
 0123456789012345678901234567890123456789012345678901234567890123
I (509) view: Plot: Length=512, min=-60.000000, max=40.000000
W (519) main: Signals x1 and x2 on one plot
I (519) view: Data min[405] = -31.928421, Data max[1] = 10.407180
 ________________________________________________________________
0                                                                |
1                                                                |
2| |                                                          | ||
3| |||   | ||||||| ||||||||| |||| || ||||||| || ||   |||||   |||||
4 |||||||||||||||||||||||||||||||||||||||||||||||| ||||||||||||| |
5 | | |||     ||| |     |       |   |    |    ||  ||| |  ||||    |
6                                                 |              |
7                                                                |
8                                                                |
9                                                                |
 0123456789012345678901234567890123456789012345678901234567890123
I (599) view: Plot: Length=512, min=-60.000000, max=40.000000
I (609) main: FFT for 1024 complex points take 130110 cycles
I (609) main: End Example.

esp-dsp library question (DSP-85)

These marcros are from CIMSIS-DSP
arm_cfft_sR_f32_len256
arm_cfft_instance_f32
arm_cfft_f32

My question is what is the equivalent of those macros with esp-dsp library?

Thanks,

[Question] Decimation step in dsps_fird_f32_ae32 (DSP-86)

In the implementation of this FIR function with decimation support, I have following questions:

(1) Is decimation applied before FIR filtering or after FIR filtering?
(2) Say I have sampling rate of 10KHz (10K samples collected in one sec), and I want to use decimation factor of 10 for an output filtered array of 1K samples per sec, then do I design FIR coefficients corresponding to 10KHz sampling or 1KHz sampling?

The issue is that my desired filtering range is 0-500Hz and filter response is very different when choosing 10KHz vs 1KHz sampling rate for FIR coefficients. What is the correct sampling rate to design FIR coefficients for when using this decimation function?

(3) Does the setup of FIR using

esp_err_t dsps_fird_init_f32((fir_f32_t) *fir, float *coeffs, float *delay, int N, int decim, int start_pos)

does N need to be an odd number? In several implementations of FIR, N must be an odd number.

Request: Is it possible to use ESP-DSP in Arduino for ESP32?

My questions:

1. is it possible to use ESP-DSP in Arduino code, similar to other ESP-IDF code?
2. if yes, can you make a basic example I could follow?

Hello, I have made a working spectrum analyzer using ArduinoFFT (link) which is obviously not optimized for ESP32. Similar to this man's work. In my case I use it to drive an LED strip.

I generally do not use ESP-IDF as it is very confusing for me, however I am aware that some ESP-IDF functions are still accessible in the arduinoespressif32 framework. Is this possible with ESP-DSP?

I am actually attempting to use it right now, but as I am not a professional programmer my progress is very slow. A lot of compiler errors and definition errors etc. It will probably take me a week to do (badly) what you can do (properly) in an hour. So my request is: can you make an example using ESP-DSP FFT in Arduino? Similar to this ArduinoFFT example, reading values from an analog pin and running FFT on them.

Context: the ESP32 dev boards I bought are defective, locked at 160MHz from the factory. If the ESP-DSP code offers a performance boost that would be great.
I use arduinoespressif32 framework in PlatformIO compiler, if that makes a difference.

Enhancement: ESP-DSP *really* needs high-performance sin()/cos() (DSP-70)

I've implemented a DSP application in an ESP32 using ESP-DSP (using vector math and FIRs), and the performance is very good, comparable to STM32F446x using CMSIS-DSP when scaled for clock frequency - very impressed!

However, one thing that DSP applications often do is mix a signal with an I/Q 'oscillator' implemented as in dsps_tone_gen_f32(), except both the sin() and cos() are calculated together. I noticed the performance of the sin() and cos() library functions is not optimized and very poor. My estimate is that sin() and cos() each take ~2060 clocks per call, a total of ~4120 clocks per I/Q calculation.

As an experiment, I built the ARM CMSIS-DSP optimized arm_sin_f32() and arm_cos_f32() and these take ~225 clocks per call, a total of ~450 clocks per I/Q calculation, a little greater than 9x the performance.

ESP-DSP would be greatly enhanced with the addition of optimized sin()/cos() functions, perhaps even as a single function that returns both the sin() and cos() of the same input.

Thank you!
Dana

Efficient IIR filter bank design?

Hi,

I was wondering if someone could point me in the right direction for designing an IIR-based filter bank. My goal is to recreate the MSGQ7's 7-band peak detection using the esp-dsp library.

I originally semi-successfully used this library's FFT function, but I couldn't get the resolution I needed in lower frequencies as I noted in this reddit post. I'm no expert in DSP, but a reddit user told me that a 44100fs/1024 point FFT yields a 20ms FFT frame window, and low-period frequencies (<200hz) would cause oscillations in the lower bins. This is exacerbated by spectral leakage.

As suggested in the reddit post, I moved to using this library's IIR filter. For each of the 7 MSGEQ7 bands (datasheet here) I calculated the coefficients using this handy online IIR biquad filter calculator. My "peak detector" logic for 63hz (which is just an average of all frequencies in a bandpass filter output) is as follows:

#define N_SAMPLES (2048)
#define N_SAMPLES_HALF (1024)

float *filter_output = (float *)calloc(N_SAMPLES_HALF, sizeof(float));
float *y_cf = (float *)calloc(N_SAMPLES, sizeof(float));

// x1 continuously updated from bluetooth a2dp i2s stream in my case
float *x1 = (float *)calloc(N_SAMPLES_HALF, sizeof(float));

float coeffs[5] = {
  0.0004485915993143372,
  0,
  -0.0004485915993143372,
  -1.9990222852850883,
  0.9991028168013714,
};

void calculate_average() {
  float w_lpf[5] = {0, 0};
  dsps_biquad_f32(x1, filter_output, N_SAMPLES_HALF, coeffs, w_lpf);

  for (int i = 0; i < N_SAMPLES_HALF; i++) {
    y_cf[i * 2 + 0] = filter_output[i];
    y_cf[i * 2 + 1] = 0;
  }

  dsps_fft2r_fc32(y_cf, N_SAMPLES_HALF);
  dsps_bit_rev_fc32(y_cf, N_SAMPLES_HALF);

  for (int i = 0; i < N_SAMPLES_HALF / 2; i++) {
    avg += (y_cf[i * 2 + 0] * y_cf[i * 2 + 0] + y_cf[i * 2 + 1] * y_cf[i * 2 + 1]) / N_SAMPLES_HALF;
  }
  avg /= N_SAMPLES_HALF;
  printf("%f\n", avg);
}

My question is (and maybe @dmitry1945 you could help me out): is there a more efficient way to do this? Ultimately to get 7 bands (or more), I would need to loop over this 7 times and calculate an IIR filter and FFT before averaging the FFT results. This seems horribly inefficient, but I just don't know enough about IIR filter bank design to know any better.

Alternatively, does anyone know how I could get better lower frequency resolution using the FFT alone? I really liked this solution (I had 1/3rd octave band and a-weighting logic running flawlessly) but I need low frequency resolution. I see that the max sampling rate of esp32 i2s is 48000 so I don't think adjusting this would help with frequency resolution. But is there anything else that I could adjust to get better lower frequency resolution in my FFT?

Any advice would be greatly appreciated! Thanks.

conv 和 corr 的实现有误 (DSP-83)

conv 和 corr 计算的实现有误。
以函数 dsps_corr_f32_ansi 为例

红框内的判断条件应该是 n <= (siglen - patlen)，否则会少算一个点，导致错误。
同理，dsps_corr_f32_ansi 的实现中也有这个错误。

Inverse of dsps_cplx2real_fc32 (DSP-99)

Request for a feature or assistance.

I learned that an optimal fft of a N real input can be done using a full fft on an N/2 input and then a call to dsps_cplx2real_fc32 .
I understand that an fft of a complex input/output can be used as an ifft with some small adjustments.

I am looking to do an efficient ifft where the output is expected to be real and the input is the same format that dsps_cplx2real_fc32 returns.
Is it possible to do it in an efficient way like it is possible with the forward direction? Do we need an inverse of dsps_cplx2real_fc32 and then a call to a full fft with N/2 values?
Please advise.

Fourier Transform for real input optimisation

We have real signal with N points. esp-fftr.zip

#include "dsps_fft2r.h"

void main()
{
    enum {N=8};
    float x1[N] = {0,1,2,3,4,5,6,7};
    float y_cf[N*2];

    dsps_fft2r_init_fc32(NULL, CONFIG_DSP_MAX_FFT_SIZE);

    for (int i = 0; i < N; i++)
    {
        y_cf[i*2 + 0] = x1[i];
        y_cf[i*2 + 1] = 0.0; // only real part
    }
    // FFT
    dsps_fft2r_fc32_ansi(y_cf, N);
    // Bit reverse
    dsps_bit_rev_fc32_ansi(y_cf, N);

    for (int i = 0 ; i < N ; i++) {
        printf("%f,%f\n", y_cf[i * 2 + 0], y_cf[i * 2 + 1]);
    }
}

Output:

28.000000,0.000000
-4.000000,9.656854
-4.000000,4.000000
-4.000000,1.656854
-4.000000,0.000000
-4.000000,-1.656854
-4.000000,-4.000000
-4.000000,-9.656855

Result is same as numpy.fft.fft(range(8)). As we can see output is symmetric. There is a special optimized function in numpy for this case called rfft. From numpy doc:

When the DFT is computed for purely real input, the output is Hermitian-symmetric, i.e. the negative frequency terms are just the complex conjugates of the corresponding positive-frequency terms, and the negative-frequency terms are therefore redundant. This function does not compute the negative frequency terms, and the length of the transformed axis of the output is therefore n//2 + 1.

It it would be great to have such rfft in esp dsp.

Maybe it's easier to show on python. This is straightforward dft:

def compute_dft_complex(input):
  n = len(input)
  output = []
  for k in range(n):  # For each output element
    s = complex(0)
    for t in range(n):  # For each input element
      angle = 2j * cmath.pi * t * k / n
      s += input[t] * cmath.exp(-angle)
    output.append(s)
  return output

This is optimised rdft:

def compute_rdft_complex(input):
  n = len(input)
  output = []
  for k in range(n//2+1):  # !!! almost 2x time faster !!!
    s = complex(0)
    for t in range(n):  # For each input element
      angle = 2j * cmath.pi * t * k / n
      s += input[t] * cmath.exp(-angle)
    output.append(s)
  return output

Test:

import cmath
import numpy as np
np.allclose(np.fft.fft(x), compute_dft_complex(x))
np.allclose(np.fft.rfft(x), compute_rdft_complex(x))

ESP-DSP optimized functions can't be found during linking(IDFGH-5484)

Environment

• Development Kit: ESP32-DevKitC
  Module or chip used: ESP32-WROOM-32
• IDF version 4.2
• Build System: idf.py
• Compiler version : xtensa-esp32-elf-gcc (crosstool-NG esp-2020r3) 8.4.0
• Operating System: WindowsPlain Command Prompt
• Using an IDE?: No|
• Power Supply: USB

Problem Description

After adding ESP-DSP component to esp-idf components, only ANSI C function can be compiled, the optimized functions couldn't be found

Expected Behavior

Be able to use optimized DSP functions

Steps to reproduce

1. Clone DSP component to idf components
2. configure the DSP to use optimized functions

3. Build any DSP example

Build output:
build_output.txt

esp-dsp library as component of esp-idf project

I want to use these libraries in my esp-idf projects. I am using PlatformIO framework of Visual Code to write my code.
As I see in the PlatformIo website https://docs.platformio.org/en/latest/frameworks/espidf.html#esp-idf-components, I clone dsp libraries in my project as a component and I add is CmakeList.txt the path to the component for including the libraries:
include($ENV{IDF_PATH}/tools/cmake/project.cmake)
list(APPEND EXTRA_COMPONENT_DIRS esp-dsp)
project(subscribe_publish)

When I build the project I see this error

-- Project is not inside a git repository, or git repository has no commits; will not use 'git describe' to determine PROJECT_VER.
CMake Error at C:/Users/.../.platformio/packages/framework-espidf/tools/cmake/project.cmake:277 (set):
Maximum recursion depth of 1000 exceeded
Call Stack (most recent call first):
C:/Users/.../.platformio/packages/framework-espidf/tools/cmake/project.cmake:278 (__project)

This line C:/Users/.../.platformio/packages/framework-espidf/tools/cmake/project.cmake:278 (__project) refers to this line of thee file project.cmake:
function(project)
set(project_ARGV ARGV)
__project(${${project_ARGV}})

Compile of examples fail

[ 89%] Built target __idf_wifi_provisioning
In file included from /esp-dsp/modules/support/view/dsps_view.cpp:3:
/esp-dsp/modules/support/view/dsps_view.cpp: In function 'void dsps_view(const float*, int32_t, int, int, float, float, char)':
/esp-idf/components/log/include/esp_log.h:265:27: error: format '%i' expects argument of type 'int', but argument 6 has type 'int32_t' {aka 'long int'} [-Werror=format=]
265 | #define LOG_COLOR(COLOR) "\033[0;" COLOR "m"

Need to remove noise from audio signal using IIR low pass filter(esp-dsp library) (DSP-87)

Hi

Hope you are doing good.

esp-idf version = stable release 4.4.1
Dev-Kit = https://github.com/W00ng/ESP32-S3-HMI-DevKit

I am using above mentioned kit and esp-idf version for my Project. Actually I need to record audio from stereo mic and play the same audio after noise filtering (I am using esp-dsp library and IIR-LPF method for the same ). But I am still getting noise after low pass filtering. I think I am missing something or I am doing something wrong configurations.

I2S configurations are as following.

#define I2S_CONFIG_DEFAULT() { \
    .mode                   = I2S_MODE_MASTER | I2S_MODE_TX | I2S_MODE_RX, \
    .sample_rate            = sample_rate, \                      /* sampling rate is 16000 (16k)*/
    .bits_per_sample        = I2S_BITS_PER_SAMPLE_16BIT, \
    .channel_format         = I2S_CHANNEL_FMT_RIGHT_LEFT, \
    .communication_format   = I2S_COMM_FORMAT_STAND_I2S, \
    .intr_alloc_flags       = ESP_INTR_FLAG_LEVEL1, \
    .dma_buf_count          = 6, \
    .dma_buf_len            = 160, \
    .use_apll               = false, \
    .tx_desc_auto_clear     = true, \
    .fixed_mclk             = 0, \
    .mclk_multiple          = I2S_MCLK_MULTIPLE_DEFAULT, \
    .bits_per_chan          = I2S_BITS_PER_CHAN_16BIT, \
}

Audio record and play task is as following.

void audio_record_task(void *args)
{
    static esp_err_t ret;
    static size_t bytes_read = 0;
    static size_t bytes_write = 0;
    while (1) 
    {

        if (mode == record) {
            ESP_LOGI(TAG, "record start");
            audio_index = 0;
            while ((mode == record) && (audio_index < (BUF_SIZE - 	FRAME_SIZE)))
            {
                ret = i2s_read(I2S_NUM_0, audio_buffer + audio_index, FRAME_SIZE, &bytes_read, 100);
                if (ret != ESP_OK) {
                    ESP_LOGE(TAG, "[echo] i2s read failed");
                    abort();
                }
                audio_index += FRAME_SIZE;
            }
            if (mode == record) mode = idle;
            ESP_LOGI(TAG, "record end");
        }
        else if (mode == play)
        {
            ESP_LOGI(TAG, "play start");
            ESP_LOGI(TAG, "audio_index = %d", audio_index);
            audio_total = audio_index;  //recorder length
            audio_index = 0;
#if 1    /* IIR low pass filtering */
            esp_err_t ret = ESP_OK, ret_hpf = ESP_OK;
            float coeffs_lpf[5];
            float coeffs_hpf[5];
            float w_lpf[5] = {0,0};

            // Calculate iir filter coefficients
            ret = dsps_biquad_gen_lpf_f32(coeffs_lpf, 0.4, 0.1);
            if (ret  != ESP_OK)
            {
                ESP_LOGE(TAG, "Operation error LPF = %i", ret);
                return;
            }

            while(audio_index < audio_total)
            {
		for (int i=audio_index,j=0; (i-audio_index) < SAMPLES_NUM ; i++,j++)
		{
			d[j] = (float)audio_buffer[i];     /*filling input buffer for dsps_biquad_f32() */
		}
		// Process input signal
		ret = dsps_biquad_f32(d, y, N, coeffs_lpf, w_lpf);
		if (ret  != ESP_OK)
		{
			ESP_LOGE(TAG, "Operation error biquad lpf= %i", ret);
			return;
		}
		for (int i=audio_index, j=0 ; (i-audio_index) < SAMPLES_NUM ; i++,j++)      /* SAMPLES_NUM = 1024 */
		{
			y[j] = y[j] * 0.1;
			audio_buffer[i] = (int16_t)y[j];     /* filling audio_buffer back with filtered output to pass it it i2s_write to play it */
		}
		audio_index += SAMPLES_NUM;
		vTaskDelay((10) / portTICK_PERIOD_MS);
            }
#endif

            audio_index = 0;
            while ((mode == play) && (audio_index < audio_total))
            {
                /* playing low-pass filtered audio signal with speaker */ 
                ret = i2s_write(I2S_NUM_0, audio_buffer + audio_index, FRAME_SIZE, &bytes_write, 100);
                if (ret != ESP_OK) {
                    ESP_LOGE(TAG, "[echo] i2s write failed");
                    abort();
                }
                audio_index += FRAME_SIZE;
            }
           if (mode == play) mode = idle;
            ESP_LOGI(TAG, "play end");
        }
        else
        {
            vTaskDelay((100) / portTICK_PERIOD_MS);  
        }
    }
    vTaskDelete(NULL);
}

When I play audio output it is actual audio signal(low voise) with noise(high voise).

@dmitry1945 I have also checked your reply in https://github.com/espressif/esp-dsp/issues/15 post, but didn't get it how it will be applicable to my code. I think I am missing something or doing something silly. Please suggest me for next step to remove noise from audio signal. Also suggest another filtering method if it is easy rather than IIR-LPF for my task.

Thanks in advance.

Current master branch example code is not compiling

I did a git clone and make of dotprod example as per README.md

git clone https://github.com/espressif/esp-dsp.git
cd esp-dsp/examples/dotprod
make

I get lots of compile errors of this type:

.../GitHub/esp-dsp/modules/fft/float/dsps_fft2r_bitrev_tables_fc32.c:579:5: error: initializer element is not constant
(uint16_t)bitrev2r_table_16_fc32_size,

I use ESP-IDF 3.3.1 and toolchain:

% xtensa-esp32-elf-gcc -v
Using built-in specs.
COLLECT_GCC=xtensa-esp32-elf-gcc
COLLECT_LTO_WRAPPER=/GitLab/CTR-01-Rel2/src/toolchain/xtensa-esp32-elf-80/bin/../libexec/gcc/xtensa-esp32-elf/5.2.0/lto-wrapper
Target: xtensa-esp32-elf
Configured with: /builds/idf/crosstool-NG/.build/src/gcc-5.2.0/configure --build=x86_64-build_pc-linux-gnu --host=x86_64-build_pc-linux-gnu --target=xtensa-esp32-elf --prefix=/builds/idf/crosstool-NG/builds/xtensa-esp32-elf --with-local-prefix=/builds/idf/crosstool-NG/builds/xtensa-esp32-elf/xtensa-esp32-elf/sysroot --with-sysroot=/builds/idf/crosstool-NG/builds/xtensa-esp32-elf/xtensa-esp32-elf/sysroot --with-newlib --enable-threads=no --disable-shared --with-pkgversion='crosstool-NG crosstool-ng-1.22.0-80-g6c4433a' --disable-__cxa_atexit --enable-cxx-flags='-fno-rtti -ffunction-sections' --with-gmp=/builds/idf/crosstool-NG/.build/xtensa-esp32-elf/buildtools --with-mpfr=/builds/idf/crosstool-NG/.build/xtensa-esp32-elf/buildtools --with-mpc=/builds/idf/crosstool-NG/.build/xtensa-esp32-elf/buildtools --with-isl=/builds/idf/crosstool-NG/.build/xtensa-esp32-elf/buildtools --with-cloog=/builds/idf/crosstool-NG/.build/xtensa-esp32-elf/buildtools --with-libelf=/builds/idf/crosstool-NG/.build/xtensa-esp32-elf/buildtools --enable-lto --enable-target-optspace --without-long-double-128 --disable-libgomp --disable-libmudflap --disable-libssp --disable-libquadmath --disable-libquadmath-support --disable-nls --enable-languages=c,c++ --disable-libstdcxx-verbose --enable-threads=posix --enable-gcov-custom-rtio
Thread model: posix
gcc version 5.2.0 (crosstool-NG crosstool-ng-1.22.0-80-g6c4433a)

dsps_fft2r_sc16_ansi_ should malloc aligned memory? (DSP-93)

esp-dsp/modules/fft/fixed/dsps_fft2r_sc16_ansi.c

Line 92 in 401faf8

dsps_fft_w_table_sc16 = (int16_t*)malloc(CONFIG_DSP_MAX_FFT_SIZE*sizeof(int16_t));

For use with function dsps_fft2r_sc16_aes3 should the init function be using 16 byte aligned memory?

Where can I access an assembler language reference manual of esp32 cpu?(Please support features of the 'vector add' and 'vector multiplication', not only dot product)

Where can I access an assembler language reference manual of esp32 cpu?
Or
Please support features of the 'vector add' and 'vector multiplication', not only dot product.

dsps_fir_f32_aes3 is not implemented (DSP-79)

In v1.2.0-1-g07aa7b1 of the esp-dsp some functions have an aes3 version, optimized for the ESP32-S3, using 128-bit vector instructions. The dotproduct is one of them. There is also a dsps_fir_f32_aes3.S file, but this is apparently not finished. Is there a chance to have an S3-optimized version of it anytime soon?

Missing <cmath> header in modules/matrix/mat/mat.cpp

Environment

• Development Kit: ESP32-LyraT
• IDF version v3.3
• Build System: Make
• Compiler version 1.22.0-80-g6c4433a
• Operating System: Windows and Linux
• Power Supply: USB

Problem Description

Unable to compile due to abs is not a member of std error. More details are available in the forums: https://esp32.com/viewtopic.php?f=20&t=12499

I will submit a PR shortly that resolves the issue on my copy

Doesn't compile with IDF v5.0

Since the removal of soc/cpu.h in IDF v5.0, this component can't be compiled. Can someone one fix it.

dot product example doesn't really compute n!

The dot product in the esp-dsp/examples/dotprod/main/dsps_dotproduct_main.c file won't compute n! as the comment says, it will just compute the addition of all numbers from 0 to 255.

Questions regarding FFT Api (DSP-95)

First of all thanks for providing this API.
I want to use the FFT api on an esp32-s3 but there are some things that I struggle to understand.

I will be referencing to pages from this article: https://www.sjsu.edu/people/burford.furman/docs/me120/FFT_tutorial_NI.pdf

Here is a list of my questions

1. Why are dsps_cplx2reC and cplx2real used? What do they do? and what is the difference between them? There is conflicting documentation about this. For example, a comment in the FFT examples states that dsps_cplx2 returns two complex vectors, but the ESP-DSP Library documentation states that it returns two real arrays. Why can’t I just take the magnitude of the complex result directly after doing the FFT and bit reversal?

2. How to use the FFT with real input values? I get that i can set all the imaginary parts to 0, but this is not what is done in the fft4real example. Here all the values are simply concatenated directly after each other without “padding 0’s” in the imaginary parts (see code snippet bellow). In the fft4real example dsps_cplx2real is also used instead of dsps_cplx2reC (referring back to question 1).

    // (Snippet from fft4real example):

    // Convert two input vectors to one complex vector
    for (int i=0 ; i< N ; i++)
    {
        x1[i] = x1[i] * wind[i];
        x2[i] = x1[i];
    }

3. Is the output of the FFT single or two-sided? On the bottom of page 2 in the article I linked above, is it stated that all values located between 1 and N/2-1 on the frequency axis should be doubled in value, to convert it from from two-sided to single-sided. And all values after N/2 should be tossed away. But this is not done in the ESP-DSP FFT examples. I don't understand this.

4. Is the output of the FFT amplitude or power? On page 6 in the article I linked above, it is stated that 10 * log10 is used for power and 20 * log10 is used for amplitude when converting from linear scale to log scale. I would think the output of the FFT would be amplitude, but 10*log10 is used is used in the ESP-DSP FFT examples as if the output of the fft was Power. I don't understand this.

I would love to get some clearance on these questions.

best regards,
Galfy1

Implement a int32 version of all the conv functions (DSP-72)

I have borrowed your dsps_corr_f32_ansi implementation and made a int32 version of it for my own project.

I did this because the internal ADC, when used together with the internal I2S controller, uses 12bit integer values and to avoid converting back and forth.

Maybe an specific ae implementation would give some performance improvement compared to C implementation?

Code snippet below to show what I mean (it's a very minor modification of the variabels :D)

void corr_s32(const int32_t *Signal, const int siglen, const int32_t *Pattern, const int patlen, int32_t *dest)
{
    for (size_t n = 0; n < (siglen - patlen); n++) {
        int32_t k_corr = 0;
        for (size_t m = 0; m < patlen; m++) {
            k_corr += Signal[n + m] * Pattern[m];
        }
        dest[n] = k_corr;
    }
}

Bug: dsps_fft4r_fc32() returns incorrect values for specific number of samples (e.g. 1024, 256, 64)

The results can be reproduced by running standard fft4real example.
Below are examples of correct (#define N_SAMPLES 2048 ) and incorrect (#define N_SAMPLES 1024 ) results.
Incorrect results occur also at 256, 64 number of samples.

#define N_SAMPLES 2048

#define N_SAMPLES 1024

FFT computed peak amplitude frequency seems to be off from expected value (DSP-71)

Environment

• Module or chip used: [ESP32-WROOM-32]
• IDF version : v3.3.1
• Build System: make
• Compiler version : 5.2.0
• Operating System: [Linux]
• Power Supply: [USB]

Problem Description

The FFT computed spectral peak frequency seems to be off from true input signal frequency (pure sine wave input).

Expected Behavior

I generated a sine wave signal using the following function:

dsps_tone_gen_f32(x1, N, 5.0, 0.46, 0);

where N=1024

For a FFT with a resolution of 1 Hz (1K total samples/1KHz sampling rate), I expect accuracy of FFT output to be +/- 1Hz accuracy.

I expected FFT plot to show single peak corresponding to 460Hz (+/- 1Hz) for this signal.

Actual Behavior

I get following output showing peak amplitude corresponds to 471 Hz:

I (326) view: Data min[112] = 0.000000, Data max[471] = 2.494988

Code to reproduce this issue

        int N=1024;
        ret = dsps_fft2r_init_fc32(NULL, CONFIG_DSP_MAX_FFT_SIZE);
        // Generate hann window
        dsps_wind_hann_f32(wind, N);
        dsps_tone_gen_f32(x1, N, 5.0, 0.46,  0);
        for (int i=0 ; i< N ; i++)
        {
            y_cf[i*2 + 0] = x1[i] * wind[i];
            y_cf[i*2 + 1] = 0.0; // only real part
        }
        // FFT
        dsps_fft2r_fc32(y_cf, N);
        // Bit reverse
        dsps_bit_rev_fc32(y_cf, N);
        // Convert one complex vector to two complex vectors
        dsps_cplx2reC_fc32(y_cf, N);

        for (int i = 0 ; i < N/2 ; i++) {
            y1_cf[i] = sqrt((y_cf[i * 2 + 0] * y_cf[i * 2 + 0] + y_cf[i * 2 + 1] * y_cf[i * 2 + 1]))/N;
        }
        dsps_view(y1_cf, N/2, 128, 20,  0, 5, '|');

Debug Logs

I (326) view: Data min[112] = 0.000000, Data max[471] = 2.494988
 ________________________________________________________________________________________________________________________________
0                                                                                                                                |
1                                                                                                                                |
2                                                                                                                                |
3                                                                                                                                |
4                                                                                                                                |
5                                                                                                                                |
6                                                                                                                                |
7                                                                                                                                |
8                                                                                                                                |
9                                                                                                                     |          |
0                                                                                                                     |          |
1                                                                                                                     |          |
2                                                                                                                     |          |
3                                                                                                                     ||         |
4                                                                                                                     ||         |
5                                                                                                                     ||         |
6                                                                                                                     ||         |
7                                                                                                                     ||         |
8                                                                                                            |||||||||||||||||||||
9||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||                    |
 01234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567