commit cc793257f48b24b47c5dbcc13680b34f4d66a7f2
parent 065f3c754a42919e2ea867adfb1aa649f39e4783
Author: Matsuda Kenji <info@mtkn.jp>
Date: Thu, 20 Apr 2023 11:46:22 +0900
update
Diffstat:
3 files changed, 154 insertions(+), 2 deletions(-)
diff --git a/man/draft/rp2040_1.html b/man/draft/rp2040_1.html
@@ -44,6 +44,7 @@ RP2040は電源を入れるといくつかの段階(ここでは関係ないの
</p>
<h2>CRC32(巡回冗長検査)</h2>
+<h3>基本</h3>
<p>
入力のデータをごにょごにょしてある値を出力する。\
<figure>
@@ -104,7 +105,91 @@ RP2040は電源を入れるといくつかの段階(ここでは関係ないの
----
000 CRC3チェックサム
</code></pre>
+<p>
+普通の割り算と基本は同じであるが、引き算の部分だけXORになっている。\
+</p>
+
+<h3>細かいこと</h3>
+<p>
+以上の計算をプログラムの先頭252バイトに対して、33bitの除数を用いて行う。\
+データの並べ方は、上の例において左側を先頭に、フラッシュROM上の0番地から順に、\
+各バイトは最上位ビットから順に並べる。\
+入力のデータは253バイト目から256バイト目に<code>0</code>をひっつけて計算する。\
+これは多分<code>for</code>ループを252回回す都合かな？\
+除数は<code>0x104c11db7</code>である(最上位ビットは常に1なのでデータシート\
+では省略されている)。\
+</p>
+<p>
+入力データは1バイトづつ処理したいみたいである。多分通信等で使う都合である。\
+この時XORは結合則が成り立つので1バイト処理した結果を8ビットシフトしたものと\
+次のバイトとをXORして次の処理の入力として利用することができる:
+</p>
+<pre><code>\
+111000111000000110000110111000111000001010010011111000111000000110010011 入力(適当)
+|......|
+111000110000000000000000000000000000000000000000000000000000000000000000 先頭1バイト
+100000100110000010001110110110111 除数
+------------------------------------------------------------------------
+011000010110000010001110110110111
+ 100000100110000010001110110110111
+ -----------------------------------------------------------------------
+ 010000001010000110010011011011001
+ 100000100110000010001110110110111
+ ----------------------------------------------------------------------
+ 000000110010001110101000000000101
+|......|
+ 000000110010001110101000000000101 1バイト目の結果
+ |......|
+ 10000001 入力の2バイト目
+ ----------------------------------------------------------------
+ 100000100010001110101000000000101 1バイト目の結果と2バイト目のXOR
+ 100000100110000010001110110110111 除数
+ ----------------------------------------------------------------
+ 000000000100001100100110110110010
+ .
+ .
+ .
+</code></pre>
+<p>
+以上の操作は以下のようなアルゴリズムのループで実装できる。\
+</p>
+<ul>
+<li>前回の結果と、入力データの次のバイトをXOR</li>
+<li>
+ <ul>
+ <li>先頭の1ビットが1の場合、除数とXORを取りシフト</li>
+ <li>先頭の1ビットが0の場合、そのままシフト</li>
+ </ul>
+</li>
+</ul>
+<p>
+これを<code>for</code>ループで回す都合上、最初のバイトもXORを取る。\
+上の例では最初は<code>0x0</code>とXORを取っているが、この値を<code>0x0</code>\
+以外にすることもできる。そうした方がいろいろいいこともあるらしい。\
+RP2040では<code>0xffffffff</code>を使う。\
+</p>
+<p>
+これを実装したのが以下のコード:\
+</p>
+<pre><code>\
+uint32_t
+crc32(uint8_t *idata, size_t len)
+{
+ uint32_t pol = 0x04C11DB7;
+ uint32_t c = 0xFFFFFFFF;
+ uint32_t b;
+ for (int i = 0; i < len; i++) {
+ b = idata[i] << 24;
+ c ^= b;
+ for (int j = 0; j < 8; j++) {
+ c = c >> 31 & 1 ? c << 1 ^ pol : c << 1;
+ }
+ }
+
+ return c;
+}
+</code></pre>
<h2>UF2</h2>
diff --git a/pub/draft/rp2040_1.html b/pub/draft/rp2040_1.html
@@ -43,6 +43,7 @@ RP2040は電源を入れるといくつかの段階(ここでは関係ないの
</p>
<h2>CRC32(巡回冗長検査)</h2>
+<h3>基本</h3>
<p>
入力のデータをごにょごにょしてある値を出力する。<figure>
<blockquote cite="https://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E5%86%97%E9%95%B7%E6%A4%9C%E6%9F%BB">
@@ -96,7 +97,73 @@ RP2040は電源を入れるといくつかの段階(ここでは関係ないの
----
000 CRC3チェックサム
</code></pre>
+<p>
+普通の割り算と基本は同じであるが、引き算の部分だけXORになっている。</p>
+<h3>細かいこと</h3>
+<p>
+以上の計算をプログラムの先頭252バイトに対して、33bitの除数を用いて行う。データの並べ方は、上の例において左側を先頭に、フラッシュROM上の0番地から順に、各バイトは最上位ビットから順に並べる。入力のデータは253バイト目から256バイト目に<code>0</code>をひっつけて計算する。これは多分<code>for</code>ループを252回回す都合かな？除数は<code>0x104c11db7</code>である(最上位ビットは常に1なのでデータシートでは省略されている)。</p>
+<p>
+入力データは1バイトづつ処理したいみたいである。多分通信等で使う都合である。この時XORは結合則が成り立つので1バイト処理した結果を8ビットシフトしたものと次のバイトとをXORして次の処理の入力として利用することができる:
+</p>
+<pre><code>111000111000000110000110111000111000001010010011111000111000000110010011 入力(適当)
+|......|
+111000110000000000000000000000000000000000000000000000000000000000000000 先頭1バイト
+100000100110000010001110110110111 除数
+------------------------------------------------------------------------
+011000010110000010001110110110111
+ 100000100110000010001110110110111
+ -----------------------------------------------------------------------
+ 010000001010000110010011011011001
+ 100000100110000010001110110110111
+ ----------------------------------------------------------------------
+ 000000110010001110101000000000101
+|......|
+ 000000110010001110101000000000101 1バイト目の結果
+ |......|
+ 10000001 入力の2バイト目
+ ----------------------------------------------------------------
+ 100000100010001110101000000000101 1バイト目の結果と2バイト目のXOR
+ 100000100110000010001110110110111 除数
+ ----------------------------------------------------------------
+ 000000000100001100100110110110010
+ .
+ .
+ .
+</code></pre>
+<p>
+以上の操作は以下のようなアルゴリズムのループで実装できる。</p>
+<ul>
+<li>前回の結果と、入力データの次のバイトをXOR</li>
+<li>
+ <ul>
+ <li>先頭の1ビットが1の場合、除数とXORを取りシフト</li>
+ <li>先頭の1ビットが0の場合、そのままシフト</li>
+ </ul>
+</li>
+</ul>
+<p>
+これを<code>for</code>ループで回す都合上、最初のバイトもXORを取る。上の例では最初は<code>0x0</code>とXORを取っているが、この値を<code>0x0</code>以外にすることもできる。そうした方がいろいろいいこともあるらしい。RP2040では<code>0xffffffff</code>を使う。</p>
+<p>
+これを実装したのが以下のコード:</p>
+<pre><code>uint32_t
+crc32(uint8_t *idata, size_t len)
+{
+ uint32_t pol = 0x04C11DB7;
+ uint32_t c = 0xFFFFFFFF;
+ uint32_t b;
+
+ for (int i = 0; i < len; i++) {
+ b = idata[i] << 24;
+ c ^= b;
+ for (int j = 0; j < 8; j++) {
+ c = c >> 31 & 1 ? c << 1 ^ pol : c << 1;
+ }
+ }
+
+ return c;
+}
+</code></pre>
<h2>UF2</h2>
diff --git a/pub/rss.xml b/pub/rss.xml
@@ -5,8 +5,8 @@
<description>ウェブページの更新履歴</description>
<language>ja-jp</language>
<link>https://www.mtkn.jp</link>
-<lastBuildDate>Thu, 20 Apr 2023 07:43:07 +0900</lastBuildDate>
-<pubDate>Thu, 20 Apr 2023 07:43:07 +0900</pubDate>
+<lastBuildDate>Thu, 20 Apr 2023 11:46:06 +0900</lastBuildDate>
+<pubDate>Thu, 20 Apr 2023 11:46:06 +0900</pubDate>
<docs>https://www.rssboard.org/rss-specification</docs>
<item>
<title>Xlibで遊んでみる6</title>
