[電子工作]LPC11U37でのXorshiftのメモリ消費量とかを調べた

　ちょっと気になったので、Xorshiftのコードサイズがどれくらいになるのか確かめてみました。あと最初うまくいかなかった時に何をしたのかの、ログです。

ぜんたいのこうせい
1)前置き
2)ソース
3)実行結果
4)まとめ
5)おまけ

使った環境
MPU : LPC11U37/401 Cortex-M0
Toolchain : Keil MDK-ARM Version:4.72.1.0

1)前置き - なんでXorshiftか
　乱数が欲しい時は何を使えばいいんでしょうか。標準的な関数rand()は、今では精度の悪い(≒ランダム性が高くない)、使わない方がいい乱数生成器の代表になってしまいましたが、シード含めて2つの関数を呼べば乱数が出てくるので、気軽に使える乱数生成器の1つです。この気軽に使えるというのが重要で、例えばC++の標準になった乱数生成クラスだと、何回かクラスのインスタンスをゴニョゴニョして、んでもってやっと乱数が出てくる(精度はいい、らしい)感じです。これだと、PC上で実行する分にはいいけれど、メモリが少なく速度が遅いマイコンだと、本当に使えるのかと疑問になってしまいます(まあそもそもC++のこれにまだ対応していないのが多いような気もする、<random>インクルードしたらエラーになったし)。
　ということで、今回はある程度精度があって、とても高速だと言われるXorshiftというものを使ってみます。
　解説とサンプルコードは、Wikipedia(http://ja.wikipedia.org/wiki/Xorshift)にあります。
　
2)ソース

　こんなかんじのコード(main.cpp)になりました。他に、startup_LPC11U**.s、system_LPC11Uxx.c、core_cm0.c、core_cm0.h、サンプルプログラム集にあるuart.c、uart.h、type.hが必要だと思われます。

#ifdef __cplusplus
extern "C" {
#endif
 
#include "LPC11Uxx.h"
#include "uart.h"
#include 
 
void SysTick_Handler(void);
 
#ifdef __cplusplus
}
#endif

//xorshift
uint32_t xor128(){
 static uint32_t x = 123456789;
 static uint32_t y = 362436069;
 static uint32_t z = 521288629;
 static uint32_t w = 88675123;
 
 uint32_t t = x ^ (x << 11);
 x = y;
 y = z;
 z = w;
 return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

void uart_init(uint32_t baudrate)
{
 UARTInit(baudrate);
}

//delay functions
volatile static uint32_t msTicks = 0;
void SysTick_Handler(void) { 
 msTicks++;
}

inline void delay(uint32_t delayTicks) {
 uint32_t curTicks = msTicks;
 while((msTicks - curTicks) < delayTicks);
}

//entry point
int main()
{
 SystemCoreClockUpdate();

 uart_init(9600);
 
 if(SysTick_Config(SystemCoreClock / 1000)){
  //handle error
 }
 
 while(1){
  char str[24] = {0};
  const uint32_t length = (uint32_t)(sizeof(str) / sizeof(str[0]));
  //convert uint32_t to char array.
  if(EOF != sprintf(str, "%u\r\n", xor128())){
   //send to console(UART serial).
   UARTSend((uint8_t*)str, length);
  }
  
  delay(1000);
 }
 
 return 0;
}

　このプロジェクトをまとめたものを.zip形式で上げておこうと思ったんですが、Bloggerがファイルのアップロードに対応していないらしいので、考え中です…この際意識高くgitデビューしちゃうか。

3)実行結果

　他に書くこと無いので、メモリ消費量と逆アセンブルを書いておきます。なお、これはXorshiftを使っているけれど、上のコードとは少し違うものをコンパイルした時のものです。
　途中に出てくる-O0、-O1、-O2、-O3というのは最適化の度合いで、数字が大きくなるほど最適化が書けられていきます。いらないものはバッサバッサ切り落とされちゃいます。これを設定するには、Keil μVision4なら、[Project]→[Options for Target '<project name>'...]で出てくるダイアログの、[C/C++]タブ、[Language/Code Generation]のOptimizationで設定可能です。

　また、ここに書いてある逆アセンブルはデバッグ時に表示されるものをコピー&ペーストしています。困ったことに、無償版だとこうしないと表示してくれないみたいです(参考:http://mbed.org/users/MACRUM/notebook/offline_compiler_2/)。


-O0です。
xorshift書く前
Program Size: Code=4724 RO-data=224 RW-data=172 ZI-data=676

xorshift書いた
Program Size: Code=4792 RO-data=224 RW-data=188 ZI-data=676

xorshiftをボーレートにした(強制的に使う)
Program Size: Code=4796 RO-data=224 RW-data=188 ZI-data=676


逆アセンブル
                 __rt_exit_exit:
0x00000160 BC03      POP      {r0-r1}
0x00000162 F001F8F3  BL.W     _sys_exit (0x0000134C)
0x00000166 0000      MOVS     r0,r0
    19:         uint32_t t = x ^ (x << 11); 
0x00000168 484E      LDR      r0,[pc,#312]  ; @0x000002A4
0x0000016A 6800      LDR      r0,[r0,#0x00]
0x0000016C 02C0      LSLS     r0,r0,#11
0x0000016E 4A4D      LDR      r2,[pc,#308]  ; @0x000002A4
0x00000170 6812      LDR      r2,[r2,#0x00]
0x00000172 4050      EORS     r0,r0,r2
0x00000174 4601      MOV      r1,r0
    20:         x = y; 
0x00000176 484C      LDR      r0,[pc,#304]  ; @0x000002A8
0x00000178 6800      LDR      r0,[r0,#0x00]
0x0000017A 4A4A      LDR      r2,[pc,#296]  ; @0x000002A4
0x0000017C 6010      STR      r0,[r2,#0x00]
    21:         y = z; 
0x0000017E 484B      LDR      r0,[pc,#300]  ; @0x000002AC
0x00000180 6800      LDR      r0,[r0,#0x00]
0x00000182 4A49      LDR      r2,[pc,#292]  ; @0x000002A8
0x00000184 6010      STR      r0,[r2,#0x00]
    22:         z = w; 
0x00000186 484A      LDR      r0,[pc,#296]  ; @0x000002B0
0x00000188 6800      LDR      r0,[r0,#0x00]
0x0000018A 4A48      LDR      r2,[pc,#288]  ; @0x000002AC
0x0000018C 6010      STR      r0,[r2,#0x00]
    23:         return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); 
0x0000018E 4848      LDR      r0,[pc,#288]  ; @0x000002B0
0x00000190 6800      LDR      r0,[r0,#0x00]
0x00000192 0CC0      LSRS     r0,r0,#19
0x00000194 4A46      LDR      r2,[pc,#280]  ; @0x000002B0
0x00000196 6812      LDR      r2,[r2,#0x00]
0x00000198 4050      EORS     r0,r0,r2
0x0000019A 0A0A      LSRS     r2,r1,#8
0x0000019C 404A      EORS     r2,r2,r1
0x0000019E 4050      EORS     r0,r0,r2
0x000001A0 4A43      LDR      r2,[pc,#268]  ; @0x000002B0
0x000001A2 6010      STR      r0,[r2,#0x00]
    24: } 

-O3です。
xorshiftのxor128()をコメントアウトしている
Program Size: Code=3236 RO-data=236 RW-data=172 ZI-data=676

xorshiftをボーレートにしてない。
Program Size: Code=3280 RO-data=224 RW-data=188 ZI-data=676

xorshiftをボーレートにした
Program Size: Code=3280 RO-data=224 RW-data=188 ZI-data=676


逆アセンブル
    19:         uint32_t t = x ^ (x << 11); 
0x00000168 492A      LDR      r1,[pc,#168]  ; @0x00000214
0x0000016A 6848      LDR      r0,[r1,#0x04]
0x0000016C 02C2      LSLS     r2,r0,#11
0x0000016E 4042      EORS     r2,r2,r0
    20:         x = y; 
0x00000170 6888      LDR      r0,[r1,#0x08]
    21:         y = z; 
0x00000172 6048      STR      r0,[r1,#0x04]
0x00000174 68C8      LDR      r0,[r1,#0x0C]
    22:         z = w; 
0x00000176 6088      STR      r0,[r1,#0x08]
0x00000178 690B      LDR      r3,[r1,#0x10]
    23:         return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); 
0x0000017A 60CB      STR      r3,[r1,#0x0C]
0x0000017C 0CD8      LSRS     r0,r3,#19
0x0000017E 4058      EORS     r0,r0,r3
0x00000180 0A13      LSRS     r3,r2,#8
0x00000182 4053      EORS     r3,r3,r2
0x00000184 4058      EORS     r0,r0,r3
0x00000186 6108      STR      r0,[r1,#0x10]
    24: } 
    25:  
    
0x00000214 0000      DCW      0x0000}#0x10]                            /* Function successful */ SysTick Timer */ 

ちなみに、Global Symbolsによれば(<project name>.map。プロジェクトをダブルクリックすると表示される。)

Symbol Name                              Value     Ov Type        Size  Object(Section)
-O3 xor128()                                 0x00000169   Thumb Code    34  main.o(.text)
-O2  xor128()                                 0x00000169   Thumb Code    34  main.o(.text)
-O1  xor128()                                 0x00000169   Thumb Code    34  main.o(.text)
-O0 xor128()                                 0x00000169   Thumb Code    62  main.o(.text)

また、static変数は
Image Symbol Table

    Local Symbols

    Symbol Name                              Value     Ov Type        Size  Object(Section)
    x                                        0x10000004   Data           4  main.o(.data)
    y                                        0x10000008   Data           4  main.o(.data)
    z                                        0x1000000c   Data           4  main.o(.data)
    w                                       0x10000010   Data           4  main.o(.data)
のようになっている。uint32_tだから4Byteなのは妥当。だけどどこで初期化されているんだろう？

　UARTがなんか動かないので、まだxor128()がちゃんと乱数を生成しているかまでは検証していない。UARTでXorshiftが動いてるのを確認しました。

Xorshift

4)まとめ

　50Bytesとかだったら、余裕でプログラムに組み込んでいける。
　1clk = 48MHzとして、1clk1命令だとする(どうなんだろう)。すると、約21nsで1命令。16命令あるから、21*16=0.336μsが理想の動作速度？

　問題はx、y、zとかのシード値をどうするかで、C++11の<random>なら、ハードウェアエントロピーリソースを用いた予測不可能な乱数std::random_deviceが使えますが、ああいったものを考えないと毎回同じ数値が出てきてしまいます。1000回ごとにEEPROMに保存して、次回はそれをシードにするとかでしょうか…


------------------------------------------------------------------------------------------------------
5)おまけ！ - extern "C"を忘れて、SysTick_Handlerが無限ループしてた話

　上のコードは、最初は次のようなコードでした。しかしこれだと、UARTに1~2文字ほど表示されるだけで動作が止まってしまい、ちゃんとxor128()が動いているのかわかりませんでした。

#ifdef __cplusplus
extern "C" {
#endif
 
#include "LPC11Uxx.h"
#include "uart.h"
#include < stdio.h >
 
 
#ifdef __cplusplus
}
#endif

//xorshift
uint32_t xor128(){
 static uint32_t x = 123456789;
 static uint32_t y = 362436069;
 static uint32_t z = 521288629;
 static uint32_t w = 88675123;
 
 uint32_t t = x ^ (x << 11);
 x = y;
 y = z;
 z = w;
 return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

void uart_init(uint32_t baudrate)
{
 UARTInit(baudrate);
}

//delay functions
volatile static uint32_t msTicks = 0;
void SysTick_Handler(void) { 
 msTicks++;
}

inline void delay(uint32_t delayTicks) {
 uint32_t curTicks = msTicks;
 while((msTicks - curTicks) < delayTicks);
}

//entry point
int main()
{
 SystemCoreClockUpdate();

 uart_init(9600);
 
 if(SysTick_Config(SystemCoreClock / 1000)){
  //handle error
 }
 
 while(1){
  char str[24] = {0};
  const uint32_t length = (uint32_t)(sizeof(str) / sizeof(str[0]));
  //convert uint32_t to char array.
  if(EOF != sprintf(str, "%u\r\n", xor128())){
   //send to console(UART serial).
   UARTSend((uint8_t*)str, length);
  }
  
  delay(1000);
 }
 
 return 0;
}

この方(http://mibc.blog.fc2.com/blog-entry-82.html)と似たような症状なのかな。

5-1)問題を切り分けたい…

　とりあえず、デバッガを起動して実行してみます。すると、デバッガのステップ実行ではうまく文字が送信されるのに、リリース(FlashへのDownload書き込み)では動かない事がわかりました。
　どこに問題があるんでしょうか…。とりあえずブレークポイントを全て消し、プログラムをしばらく走らせ、徐ろにStopさせます。すると、SysTick_Handler()のB命令でずっと止まっているのがわかりました。本来ならばmsTicks++;が実行されるだけなので、なんか変です…

　しょうが無いのでプログラムで問題がありそうなところをコメントアウトしていきます。すると、次の部分をコメントアウトしたら動きました。

if(SysTick_Config(SystemCoreClock / 1000)){
 //handle error
}

ということは、SysTick_Config()が原因みたいです。SysTick_Config()はSysTickタイマーを設定・開始させる関数なので、もしかしたら割り込みが悪い影響を与えているのかもしれません。例えば、UART送信中に割り込みが来たりしたら動かなくなるとか？(違った)
　ということで、UARTSendのところに

__disable_irq();
UARTSend((uint8_t*)str, length);
__enable_irq(); //割り込みを再設定しないといけない？

としてみました。すると、最初の1回だけは正常に動きます。どうやら、問題はUARTSendではないようです(ライブラリからコピーしてきたので動いて当たり前か…)。

　で、SysTick_Handler()が無限ループになることも考えると、UART送信中にSysTickタイマの割り込みが発生し、SysTick_Handler()に飛んで無限ループに陥るために、送信できないのかもしれないと考えます。

5-2)void SysTick_Handler(void)はどこなのか

　startup_LPC11Uxx.sではSysTick_Handler()は
SysTick_Handler PROC
                EXPORT  SysTick_Handler           [WEAK]
                B       .
                ENDP
となっています。EXPORT SysTick_Handlerを右クリックし、[Go To Definition of 'SysTick_Handler'...]を選んでみても、ちゃんとmain.cppにあるSysTick_Handlerに飛びます。
その割には、逆アセンブルを見ると、
   151:                 EXPORT  PendSV_Handler            [WEAK] 
0x0000030A E7FE      B        SVC_Handler (0x0000030A)
   152:                 B       . 
   153:                 ENDP 
   154: SysTick_Handler PROC 
   155:                 EXPORT  SysTick_Handler           [WEAK] 
0x0000030C E7FE      B        PendSV_Handler (0x0000030C)
   156:                 B       . 
   157:                 ENDP 
   158: Reserved_IRQHandler PROC 
   159:                 EXPORT  Reserved_IRQHandler       [WEAK] 
0x0000030E E7FE      B        SysTick_Handler (0x0000030E)
   160:                 B       . 
0x00000310 E7FE      B        Reserved_IRQHandler (0x00000310)
となっています。これは、main.cppで定義したSysTick_Handler()ではなく、無限ループなのでは？

　アプリケーションノートのp.424~425とp.426の"Figure 23?80 Vector table"には、SysTickの割り込みベクタは0x0000003Cらしいですが、このアドレスを見る限りだと
0x0000003C 030F      DCW      0x030F
0x0000003E 0000      DCW      0x0000
となっているので、
    32: //delay functions 
    33: volatile static uint32_t msTicks = 0; 
    34: void SysTick_Handler(void) {  
0x000001C0 BD10      POP      {r4,pc}
    35:         msTicks++; 
0x000001C2 4844      LDR      r0,[pc,#272]  ; @0x000002D4
0x000001C4 6800      LDR      r0,[r0,#0x00]
0x000001C6 1C40      ADDS     r0,r0,#1
0x000001C8 4942      LDR      r1,[pc,#264]  ; @0x000002D4
0x000001CA 6008      STR      r0,[r1,#0x00]
    36: } 
にはどう考えても飛ばなさそうです。

5-3)顛末

　ここで、SysTick_Handler()の設定の仕方に何か問題があるのではと調べたら、これが出てきました。この通りにextern "C"したらちゃんと動きました。そうだった、前も同じミスをやったんでした。完全にバカですね。

　実際に動かない場合の.mapファイルを見てみると、関数は
    xor128()                                 0x00000179   Thumb Code    62  main.o(.text)
    uart_init(unsigned)                      0x000001b7   Thumb Code    12  main.o(.text)
    SysTick_Handler()                        0x000001c3   Thumb Code    12  main.o(.text)
    main                                     0x000001cf   Thumb Code   132  main.o(.text)
    __use_two_region_memory                  0x000002f1   Thumb Code     2  heapauxi.o(.text)
    __rt_heap_escrow$2region                 0x000002f3   Thumb Code     2  heapauxi.o(.text)
    __rt_heap_expand$2region                 0x000002f5   Thumb Code     2  heapauxi.o(.text)
    __I$use$semihosting                      0x000002f7   Thumb Code     0  use_no_semi.o(.text)
    __use_no_semihosting_swi                 0x000002f7   Thumb Code     2  use_no_semi.o(.text)
    __semihosting_library_function           0x000002f9   Thumb Code     0  indicate_semi.o(.text)
    Reset_Handler                            0x00000301   Thumb Code     8  startup_lpc11uxx.o(.text)
    HardFault_Handler                        0x00000309   Thumb Code     2  startup_lpc11uxx.o(.text)
    SVC_Handler                              0x0000030b   Thumb Code     2  startup_lpc11uxx.o(.text)
    PendSV_Handler                           0x0000030d   Thumb Code     2  startup_lpc11uxx.o(.text)
    SysTick_Handler                          0x0000030f   Thumb Code     2  startup_lpc11uxx.o(.text)
となっていて、SysTick_HandlerとSysTick_Handler()が別々にあるのがわかります。