XMODEM についてのメモ
仕事でしばしばお世話になっている XMODEM の話題を(といっても、個人的な備忘録に過ぎないが)。
概要
XMODEM プロトコルは 1977 年に Ward Christensen 氏によってMODEM.ASM プログラムに実装されたプロトコルで、二つの計算機間に於けるバイナリデータの転送を目的としている。
非同期シリアル通信を用いた転送を想定しており、実際に当時は
+------+ +------+ | | シリアル +-------+ 電話回線 +-------+ シリアル | | | PC +==========+ MODEM +-----------| MODEM +==========+ PC | | | +-------+ +-------+ | | +------+ +------+
というネットワーク環境下で XMODEM を使い、電子掲示板との間でファイルを転送していたらしい*1。現在でも、シリアル経由でのちょっとした転送の際にお世話になることは多い。
その他、XMODEM には public domain で仕様が公開されていることや、実装が容易という利点がある。特に、シリアルドライバが実装済であれば、僅か 100 行程度のコードを追加するだけで転送ができるようになる手軽さは大きい。
一方で
- 128 bytes 毎に ACK/NAK をやりとりするので転送効率が悪い
- ファイル内容以外の情報(ファイル名やファイルサイズ)を渡せない*2
- 制御文字をクォートする機能がないので、ソフトウェアフロー制御と組み合わせて使用できない。
- 複数ファイルを一括して転送(バッチ転送)する機能がない。
という欠点もある。
しかし、例えば MCU の内蔵 ROM に書き込むファームウェアを転送する、といった用途であれば、
- 一般にファイルサイズは小さい。
- ファイルの送信側(ホスト PC)と受信側(ターゲット)の間はシリアルケーブルで直結という理想的な条件下で通信するので、転送過程でデータが化けることは殆どなく、従ってパケット再送は生じない。
- (受信側においては)一般にファイル名およびファイルサイズの情報は不要である。
という理由から、上記の欠点の幾つかは問題にならない。
XMODEM プロトコルには何種類かの派生プロトコルが存在するが、(個人的な主観では)以下の 2 種類が広く用いられているように思う。
- XMODEM/CRC
- XMODEM-1k
XMODEM プロトコルの仕様
以下、XMODEM プロトコルの概略について記述するが、XMODEM およびその派生プロトコルの作者らによる文書は、以下から入手できる。
XMODEM プロトコルに興味のある方は、一読されることを勧める。
その他、今回の記事の作成に際し、以下を参考にした。
通信手順
XMODEM プロトコルでは、一方がファイル送信側(以下単に送信側)、もう一方がファイル受信側(以下単に受信側)と役割を決めた上で、一対一の通信を行う。以下に通信手順の概略を示す。
1) 最初に受信側が NAK(0x15) の 1 byte を送信側に送ることで通信を開始する。
2) NAK を受けた送信側は、以下の構造を持つパケットを受信側に送る
| フィールド | バイト長 | 説明 |
|---|---|---|
| SOH | 1 | 0x01 の固定値を設定する。 受信側はこの値を以てパケットの開始を認識する。 |
| blk # | 1 | 何番目のパケットであるかを識別するための番号(所謂シーケンス番号) としての意味を持つ。最初の送信時はこのフィールド値に 1 を設定し、 以降送信する毎に、 2 -> 3 -> 4 -> … と値を 1 ずつ加算する (但し 255 の次は 0)。 |
| 255-blk # | 1 | 上記のフィールド値に対する 1 の補数(つまりビットを反転したもの)を設定する。 従って、パケットを送信する毎に 254 -> 253 -> … -> 0 -> 255 -> … となる。 |
| data | 128 | 送信するファイルの内容を設定する。 但し、ファイルのサイズが 128 の倍数でない場合、 最後のパケットに於いては不足分を Ctrl-Z(0x1a) で埋める*3。 |
| cksum | 1 | data フィールドの各バイトの値を足した値を 256 で割った余り(つまり下位 8bit)を設定する。 |
3) 2) のデータを受信した受信側は、SOH によりパケットの開始と判断し、残りの 131 bytes のデータを受信・解析した結果
- blk # および 255-blk # のフィールド値が期待したとおりか?
- data フィールド値の各バイトを合計した値の下位 8 bit を計算し、cksum フィールド値と一致するか?
を確認する。これらの条件を見たしていれば ACK(0x06) を、そうでなければ NAK(0x15) を返す。
4) 送信側は、受信側から NAK を受けた場合は、前回送信したパケットを再送する。ACK を受けた場合は、続きのデータがあれば次のパケットを送信し、そうでなければ EOT(0x04) を送信する。
5) 受信側が続きのデータのパケットを受け取った場合は 3) へ、EOT を受けた場合は ACK を返し、一連の転送処理が終了する。
例
上記の参考文献に記載されていた例を、以下に引用する。
Receiving Transmitting
Computer Computer
Ready to Ready to
Receive Transmit
| |
| |
|---------------------\NAK\--------------------->|
| |
|<------/SOH/Blk #1/Blk #1/Good Data/CkSum/------|
| |
|---------------------\ACK\--------------------->|
| |
|<------/SOH/Blk #2/Blk #2/Good Data/CkSum/------|
| |
|---------------------\ACK\--------------------->|
| |
|<------/SOH/Blk #3/Blk #3/Garbled Data/CkSum/---|
| |
|---------------------\NAK\--------------------->|
| |
|<------/SOH/Blk #3/Blk #3/Good Data/CkSum/------|
| |
|---------------------\ACK\--------------------->|
| |
|<--------------------/EOT/----------------------|
| |
|---------------------\ACK\--------------------->|
| |
V V
File File
Receipt Transmit
Ends Ends この例では、1 番目と 2 番目のパケットの転送はうまくいっているが、3 番目は転送途中でデータが化けて(garbled)しまい、受信側がこれを検出して NAK を返している。
NAK を受けた送信側は 3 番目のパケットを再送しており、今度は化けなかったため受信側は ACK を返している。
データは全体で 128×3 = 384 bytes 以下だったため、送信側は 4 番目のパケットを送ることなく EOT を返している。これで通信が終了する。
エラー処理
送信側が送信したパケットの内容が化けてしまった場合は、(既に述べた通り)受信側が NAK を返して送信側に再送させることで対処する。
それ以外のエラーとして、
- タイムアウト
- 試行回数の超過
- 受信側からの応答が化けた
が考えられる。
タイムアウトは、受信側が ACK/NAK(通信開始の NAK を含む)を送信側に応答したにもかかわらず、(断線等により)送信側からデータが届かない場合に発生する。この場合、送信側からデータが届くまで受信側は 10 秒毎に NAK を送る。
なお、受信側が NAK を 10 回連続して応答しても通信が開始されない場合、受信側はファイルの受信を諦める(つまり、受信側プログラムを再起動するなりして、明示的に再試行させない限り、送信側に NAK を投げなくなってしまう)。
受信側 -> 送信側への ACK 応答が化けた場合は、以下の方法により解決を図る:
| 送信側 | NAK 応答として扱う(つまり前回分のパケットを再送する)、 |
| 受信側 | 送信側の対処により、ACK を送ったのに前回と同じパケットが届くことになるが、 この場合は ACK を返すようにする。 |
NAK 応答が偶然 ACK に化けてしまった場合、これを受けた送信側は、受信側が期待するものより一つ進んだパケットを送信することになる。これは回復のしようがないので、後述の CAN により今までの転送分を一旦破棄し、転送を最初からやり直す。
転送処理の破棄
転送途中で回復不能なエラーを検出した場合は、CAN(0x18)を対向に送信する。CAN を送信した方も、受信した方も一連の転送処理を破棄する。
もし CAN を受信したのが受信側ならば、ACK を返して転送処理を破棄するし、
送信側ならば、次回のパケット送出時は前回の続きからではなく、最初のパケットからやり直すようにしなければならない。
なお、ACK/NAK 応答や EOT、SOH が偶然 CAN に化けてしまうと、それまでの転送分は水泡に帰す。これに対し、多くの実装では二回連続で CAN を受け取った場合のみ、転送を破棄することで対策している(本当に破棄したい場合は、二回以上連続して CAN を送るようにする必要がある)。
派生プロトコルの仕様
XMODEM/CRC
XMODEM/CRC は上記で説明した XMODEM プロトコルに、以下の変更を施したものである。
- 受信側 -> 送信側への最初の送信要求が NAK ではなく 'C'(0x43)
受信側は、転送開始時の送信要求の際、NAK の代わりに 'C' を送信する。送信側は 'C' を受信することにより、転送データを格納するパケットを、XMODEM/CRC 用のもの(後述)にする。なお、何回か*4 'C' を送っても送信側からパケットが送られてこない場合は、送信側が XMODEM/CRC プロトコルを喋れないものとして、通常の XMODEM による転送を試みる(つまり NAK を送信する)。
- 送信側 -> 受信側へのパケットのフォーマットの変更
送信側が送出するパケットに於いて、1 byte の checksum を廃し、代わりに 2 bytes の CRC-16 を付加する。
XMODEM-1k
XMODEM-1k は上記で説明した XMODEM プロトコルに、以下の変更を施したものである。
実装例
1 #include <string.h>
2 #include "sci_async.h"
3 #include "xmodem.h"
4
5 #define MAX_RETRY (9)
6
7 #define SOH (0x01)
8 #define STX (0x02)
9 #define EOT (0x04)
10 #define ACK (0x06)
11 #define NAK (0x15)
12 #define CAN (0x18)
13 #define CTRLZ (0x1a)
14
15 #define BLKNO_OFFSET (0)
16 #define INV_BLKNO_OFFSET (1)
17 #define DATA_OFFSET (2)
18 #define CSUM_OFFSET(datalen) (2 + (datalen))
19 #define CRCH_OFFSET(datalen) (2 + (datalen))
20 #define CRCL_OFFSET(datalen) (2 + (datalen) + 1)
21 #define RX_SIZE(datalen, use_crc) (2 + (datalen) + ((use_crc) ? 2 : 1))
22
23 #define FLUSH_TIMEOUT (1000)
24
25 #define MIN(a, b) ((a) < (b) ? (a) : (b))
26
27
28 static uint8_t blkbuf[1024 + 2 + 2];
29 static int pushedback = -1;
30
31 static int
32 xmodem_ungetc(int c)
33 {
34 if (c == -1)
35 return -1;
36
37 return (pushedback = (c & 0xff));
38 }
39
40 static int
41 xmodem_getc(int timeout)
42 {
43 int c;
44
45 if (pushedback != -1) {
46 c = pushedback;
47 pushedback = -1;
48 } else
49 c = sci_raw_getc(timeout);
50
51 return c;
52 }
53
54 static int
55 xmodem_putc(int c)
56 {
57 return sci_raw_putc(c);
58 }
59
60 static int
61 xmodem_read_block(uint8_t *buf, size_t n)
62 {
63 int c;
64
65 while (n-- > 0) {
66 if ((c = xmodem_getc(1000)) == -1)
67 return -1;
68 *buf++ = (uint8_t)(c & 0xff);
69 }
70
71 return 0;
72 }
73
74 static uint16_t
75 calc_crc(uint8_t *buf, size_t n)
76 {
77 uint16_t crc;
78 size_t i;
79
80 crc = 0;
81 while (n-- > 0) {
82 crc = crc ^ (uint16_t)*buf++ << 8;
83
84 for (i = 0; i < 8; i++)
85 if (crc & 0x8000)
86 crc = crc << 1 ^ 0x1021;
87 else
88 crc = crc << 1;
89 }
90
91 return (crc & 0xffff);
92 }
93
93
94 static uint8_t
95 calc_csum(uint8_t *buf, size_t n)
96 {
97 uint8_t csum;
98
99 csum = 0;
100 while (n-- > 0)
101 csum += *buf++;
102
103 return csum;
104 }
105
106 size_t
107 xmodem_rx(uint8_t *buf, size_t size, int use_crc)
108 {
109 size_t nretry;
110 uint8_t expected_blkno;
111 size_t nrecv;
112 uint16_t crch, crcl;
113 size_t datalen;
114 int c;
115
116 if (use_crc)
117 use_crc = MAX_RETRY + 1;
118
119 while (use_crc) {
120 /* mode setting handshake:
121 attempt to start XMODEM/CRC transmission */
122 xmodem_putc('C');
123
124 c = xmodem_getc(3000);
125 if ((c == SOH) || (c == STX)) {
126 xmodem_ungetc(c);
127 break;
128 }
129
130 switch (c) {
131 case CAN:
132 if ((c = xmodem_getc(3000)) == CAN) {
133 /* abort if two consecutive CAN received */
134 xmodem_putc(ACK);
135 while (xmodem_getc(FLUSH_TIMEOUT) != -1) ;
136 return 0;
137 } else
138 xmodem_ungetc(c);
139 break;
140 case EOT:
141 /* abort if EOT received */
142 xmodem_putc(ACK);
143 return 0;
144 case -1:
145 default:
146 break;
147 }
148
149 use_crc--;
150 }
151
152 if (!use_crc) {
153 /* switch to checksum mode */
154 xmodem_putc(NAK);
155 }
156
157 expected_blkno = 1;
158 nrecv = 0;
159 nretry = MAX_RETRY;
160 while ((c = xmodem_getc(10000)) != EOT) {
161 /* confirm that first octet is SOH or STX */
162 switch (c) {
163 case CAN:
164 if (xmodem_getc(10000) == CAN) {
165 /* abort if two consecutive CAN received */
166 xmodem_putc(ACK);
167 while (xmodem_getc(FLUSH_TIMEOUT) != -1) ;
168 return 0;
169 } else {
170 /* request to retransmit the block */
171 goto retrans;
172 }
173 case SOH:
174 datalen = 128;
175 break;
176 case STX:
177 if (use_crc)
178 datalen = 1024;
179 else
180 goto retrans;
181 break;
182 case -1:
183 default:
184 goto retrans;
185 }
186
187 /* read 128/1024-byte block of data */
188 if (xmodem_read_block(blkbuf, RX_SIZE(datalen, use_crc)) == -1)
189 goto retrans;
190
191 if (size < datalen) {
192 /* not enough memory left, abort it */
193 goto abort;
194 }
195
196 /* validate CRC or arithmetic checksum */
197 if (use_crc) {
198 crch = blkbuf[CRCH_OFFSET(datalen)];
199 crcl = blkbuf[CRCL_OFFSET(datalen)];
200 if (calc_crc(&blkbuf[DATA_OFFSET], datalen)
201 != ((crch << 8) | crcl))
202 goto retrans;
203 } else {
204 if (calc_csum(&blkbuf[DATA_OFFSET], datalen)
205 != blkbuf[CSUM_OFFSET(datalen)])
206 goto retrans;
207 }
208
209 /* confirm that received block# is valid */
210 if (blkbuf[INV_BLKNO_OFFSET] != (0xff - blkbuf[BLKNO_OFFSET]))
211 goto retrans;
212
213 /* confirm that sender and receiver are synchronizing */
214 if (blkbuf[BLKNO_OFFSET] == ((expected_blkno - 1) & 0xff)) {
215 /* previously sent ACK got garbled? just resend it */
216 xmodem_putc(ACK);
217 continue;
218 } else if (blkbuf[BLKNO_OFFSET] != expected_blkno) {
219 /* fatal loss of synchronization, abort it */
220 goto abort;
221 }
222
223 /* successfully received */
224 xmodem_putc(ACK);
225
226 memcpy(buf, &blkbuf[DATA_OFFSET], datalen);
227
228 buf += datalen;
229 size -= datalen;
230 nrecv += datalen;
231 expected_blkno++;
232 nretry = MAX_RETRY;
233 continue;
234
235 retrans:
236 /* something went wrong, retry or abort it */
237 if (nretry-- > 0)
238 xmodem_putc(NAK);
239 else
240 goto abort;
241 }
242
243 xmodem_putc(ACK);
244
245 return nrecv;
246
247 abort:
248 xmodem_putc(CAN);
249 xmodem_putc(CAN);
250 xmodem_putc(CAN);
251 while (xmodem_getc(FLUSH_TIMEOUT) != -1) ;
252
253 return 0;
254 }
255
256 size_t
257 xmodem_tx(const uint8_t *buf, size_t size, int use_1k)
258 {
259 size_t nsent;
260 int use_crc;
261 uint8_t blkno;
262 uint16_t crc;
263 size_t datalen;
264 uint8_t csum;
265 int c;
266 size_t i, n;
267
268 /* confirm whether receiver uses CRC or not */
269 do {
270 c = xmodem_getc(-1);
271 switch (c) {
272 case 'C':
273 use_crc = 1;
274 break;
275 case NAK:
276 use_crc = 0;
277 break;
278 case CAN:
279 if ((c = xmodem_getc(-1)) == CAN) {
280 /* abort if two consecutive CAN received */
281 xmodem_putc(ACK);
282 while (xmodem_getc(FLUSH_TIMEOUT) != -1) ;
283 return 0;
284 } else
285 xmodem_ungetc(c);
286 break;
287 case -1:
288 default:
289 break;
290 }
291 } while (c != 'C' && c != NAK);
292
293 if (!use_crc)
294 use_1k = 0;
295
296 datalen = use_1k ? 1024 : 128;
297
298 blkno = 1;
299 nsent = 0;
300 while (size > 0) {
301 xmodem_putc(use_1k ? STX : SOH);
302 xmodem_putc(blkno);
303 xmodem_putc(~blkno);
304
305 n = MIN(datalen, size);
306 for (i = 0; i < n; i++)
307 xmodem_putc((int)buf[i]);
308 for (i = n; i < datalen; i++)
309 xmodem_putc(CTRLZ);
310
311 memcpy(blkbuf, buf, n);
312 memset(&blkbuf[n], CTRLZ, datalen - n);
313 if (use_crc) {
314 crc = calc_crc(blkbuf, datalen);
315 xmodem_putc((uint8_t)((crc & 0xff00) >> 8));
316 xmodem_putc((uint8_t)(crc & 0x00ff));
317 } else {
318 csum = calc_csum(blkbuf, datalen);
319 xmodem_putc(csum);
320 }
321
322 c = xmodem_getc(-1);
323 switch (c) {
324 case CAN:
325 if (xmodem_getc(-1) == CAN) {
326 /* abort if two consecutive CAN received */
327 xmodem_putc(ACK);
328 while (xmodem_getc(FLUSH_TIMEOUT) != -1) ;
329 return 0;
330 }
331 /* otherwise, retransmit the block */
332 break;
333 case ACK:
334 /* transmit the next sequential block */
335 buf += n;
336 size -= n;
337 nsent += n;
338 blkno++;
339 break;
340 case NAK:
341 default:
342 /* retransmit the block */
343 break;
344 }
345 }
346
347 /* all data has been successfully transmitted */
348 do {
349 xmodem_putc(EOT);
350 c = xmodem_getc(-1);
351 } while (c != ACK);
352
353 return nsent;
354 } 前述のとおり、XMODEM の仕様自体が単純であるので、特に説明を要する箇所はないと思う。
上記の例では、受信側/送信側の両方の処理を実装している上、XMODEM-CRC、XMODEM-1k もサポートしているので、全体で 350 行強になっている。
しかし、実際の実装に際しては、用途に応じて
- 受信側の処理のみを実装
- エラー処理を省略
- XMODEM/CRC や XMODEM-1k は非サポート
とすればよい。この場合は 100 行前後で書けるので、実装もテストもかなり楽である。
