What goes on/what's going on:2021年04月19日分

2021/04/19(Mon)

[プログラミング] printf(3)の桁区切りはどのように実装されているのか(その1)

今回からは「'」書式指定子による桁区切りの実装について解説するのだけど、前回までのf変換のコードを元に説明するのはクソめんどくさいので、まずシンプルなd変換を実装しそいつで説明していくことにする。

このくらい初心者でもササッと書けるでしょさすがにハハッ

#define _GNU_SOURCE
#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define arraycount(array)	(sizeof(array)/sizeof(array[0]))

static inline int
to_char(int digit)
{
	return '0' + digit;
}

int
cvt_dfmt(int value, FILE *fp)
{
	/* assume INT_MIN(-2147483648) - INT_MAX(2147483647) */
	char buf[11], *s;
	unsigned int d;
	int neg;
	size_t len;

	d = (unsigned int)value;
	if ((neg = value < 0) != 0)
		d = -d;
	s = &buf[sizeof(buf)];
	do {
		assert(s > &buf[0]);
		*--s = to_char(d % 10);
		d /= 10;
	} while (d > 0);
	if (neg) {
		assert(s > &buf[0]);
		*--s = '-';
	}
	len = &buf[sizeof(buf)] - s;
	if (fwrite(s, 1, len, fp) != len)
		return 1;
	return 0;
}

int
main(void)
{
	int itest[] = {
		INT_MIN,
		-1000,
		-100,
		-10,
		-1,
		0,
		1,
		10,
		100,
		1000,
		INT_MAX
	};
	size_t i, n;
	FILE *fp;
	char *expect, *result;

	for (i = 0; i < arraycount(itest); ++i) {
		expect = NULL;
		if (asprintf(&expect, "%d", itest[i]) < 0)
			abort();
		result = NULL;
		fp = open_memstream(&result, &n);
		if (fp == NULL)
			abort();
		if (cvt_dfmt(itest[i], fp))
			abort();
		fclose(fp);
		printf("expect:[%s], result[%s]\n",
		    expect, result);
		if (strcmp(result, expect))
			abort();
		free(expect);
		free(result);
	}
	exit(EXIT_SUCCESS);
}

難しいところは何一つ無いと思う *1、符号外す時はunsigned型使うってのと、変換バッファのサイズ(-いれて11桁)をINT_MIN/INT_MAXの値を仮定した決め打ちしてる部分があるくらいか。ちなみにNのvfwprintf.cなんかだとくっそ適当に

/*
 * The size of the buffer we use as scratch space for integer
 * conversions, among other things.  Technically, we would need the
 * most space for base 10 conversions with thousands' grouping
 * characters between each pair of digits.  100 bytes is a
 * conservative overestimate even for a 128-bit uintmax_t.
 */
#define BUF     100

        CHAR_T buf[BUF];        /* buffer with space for digits of uintmax_t */

とか100あればint128_t時代がきても大丈夫でしょとかやっとるし、気にしたら負けである。

別解、あまり当チラシの裏は競技プログラミングガチ勢の方々を読者として想定していないので興奮せず着席して黙ってて頂きたいのだが、符号除いてせいぜい10桁ということで

	if (d < 10) {
		buf[0] = to_char(d);
		len = 1;
	} else if (d < 100) {
		buf[0] = to_char(d / 10);
		buf[1] = to_char(d % 10);
		len = 2;
…
	} else {
		buf[0] = to_char( d / 1000000000);
		buf[1] = to_char((d % 1000000000) / 100000000);
		buf[2] = to_char((d % 100000000) / 10000000);
		buf[3] = to_char((d % 10000000) / 1000000);
		buf[4] = to_char((d % 1000000) / 100000);
		buf[5] = to_char((d % 100000) / 10000);
		buf[6] = to_char((d % 10000) / 1000);
		buf[7] = to_char((d % 1000) / 100);
		buf[8] = to_char((d % 100) / 10);
		buf[9] = to_char( d % 10);
		len = 10;
	}

とループ展開してドヤ顔したくなる時もある、しかしお前は桁区切りの実装めんどくさくなる呪いがかかったわけだがそんなコードで大丈夫か?

そんじゃループ展開しない方のバージョンで3ケタ区切りを実装してみましょかね。

--- dcvt.c.orig	2021-04-18 16:20:00.000000000 +0900
+++ dcvt.c	2021-04-18 16:20:53.000000000 +0900
@@ -10,20 +10,27 @@
 int
 cvt_dfmt(int value, FILE *fp)
 {
-	/* assume INT_MIN(-2147483648) - INT_MAX(2147483647) */
-	char buf[11], *s;
+	/* assume INT_MIN(-2,147,483,648) - INT_MAX(2,147,483,647) */
+	char buf[14], *s;
 	unsigned int d;
-	int neg;
+	int neg, grouping;
 	size_t len;
 
 	d = (unsigned int)value;
 	if ((neg = value < 0) != 0)
 		d = -d;
 	s = &buf[sizeof(buf)];
+	grouping = 3;
 	do {
+		if (grouping == 0) {
+			assert(s > &buf[0]);
+			*--s = ',';
+			grouping = 3;
+		}
 		assert(s > &buf[0]);
 		*--s = to_char(d % 10);
 		d /= 10;
+		--grouping;
 	} while (d > 0);
 	if (neg) {
 		assert(s > &buf[0]);
@@ -68,8 +75,10 @@ main(void)
 		fclose(fp);
 		printf("expect:[%s], result[%s]\n",
 		    expect, result);
+#if 0
 		if (strcmp(result, expect))
 			abort();
+#endif
 		free(expect);
 		free(result);
 	}

こっちも難しくないよね、カウンタgroupingを3にセットして0になる度リセットとカンマを出力すりゃいいだけの話だ。

expect:[-2147483648], result[-2,147,483,648]
expect:[-1000], result[-1,000]
expect:[-100], result[-100]
expect:[-10], result[-10]
expect:[-1], result[-1]
expect:[0], result[0]
expect:[1], result[1]
expect:[10], result[10]
expect:[100], result[100]
expect:[1000], result[1,000]
expect:[2147483647], result[2,147,483,647]

それではこれで閉会!終わり!ジ・エンド!

…とはいかないんですわ、そもそも3桁ごとにカンマで区切るとかどこの田舎者の世界の話だよってな!

@そもそもどこで桁を区切るのか

有名なところではインド の山奥でっの命数法においては

日本語転写 アルファベット代用表記 デーヴァナーガリー ナスタアリーク 指数表記
ハザール hazār हज़ार ہزار 1e+03
ラーク lākh लाख لاکھ 1e+05
コルール karōṛ करोड़ کروڑ 1e+07
アラブ arab अरब ارب 1e+09
カラブ kharab खरब کھرب 1e+11
ニール nīl नील نیل 1e+13
パドマ padma पद्म پدم 1e+15
シャンク śaṅkh शंख شنکھ 1e+17

とハザール(1000)までは千進法の3桁区切りだけど、ラーク(1,00,000)以降は百進法の2桁区切りになるんだよね *2、うん国際化プログラミングにおいては桁区切りが固定位置であるという思い込みをまず捨てようか。

10,000,000(ten million)
1,00,00,000(ēk karōṛ)

ちなみにペルシャ語におけるコルールは十進ですらなく50万であるのだが、これは英米でもハーフミリオン *3とかあるし基数が10でないものは無視してよろしい。

そもそも論として日本も「一十百千」そして「万億兆」となる万進法であり4桁区切り(指数4)の命数法なのよね、アラビア数字の桁区切りは英国式に(one ten handled + million billion trillion quadrillionの)3桁(指数3の倍数)毎にやるルールだけどね。

そしてだな、以前の回で「塵劫記」に登場する日本の命数法を紹介したのを思い出してほしい。

命数 指数表記
1e+04
1e+08
1e+12
1e+16
1e+20
𥝱(秭) 1e+24
1e+28
1e+32
1e+36
1e+40
1e+44
1e+48
恒河沙 1e+56
阿僧祇 1e+64
那由他 1e+72
不可思議 1e+80
無量大数 1e+88

はい、正確には4桁区切りどころか

  • 極までは指数4(万進)
  • それ以降は指数8(万万進)

というインドと同じくめっちゃ変則な桁区切りルールによる命数法なのですわ。

なお江戸時代マンすら不便だと思ったのか、極以降を指数8とするのはごく初期の版(寛永8年版)だけで、のちに指数4に改められた(寛永11年版)ので1無量大数 = 1e+68としとるネットのどうでしたか記事の方が圧倒的に多い *4けどね。

なお塵劫記よりもはるかに巨大な数を扱う命数に華厳経(八十華厳)の「不可説不可説転」がある、1e+1037218383881977644441306597687849648128という指数からして桁あふれしとる巨大数で「悟りに必要な功徳の数」を示すもの。

まぁ今こうやってクソ記事書いてるワイ弥勒菩薩が悟りを開くという56億7千万年後のコンピューターならムーアの法則で負ける気せえへん地元やし *5およそ6億回目の改訂を経たISO-CやIEEE754ではintmax_tやbinary1145148101919…で軽々と扱えてるはずなので、その時は八十華厳のため7桁区切りを実装しないとならんのだ。

@桁区切り文字や小数点のうん国際化

これも日本では桁区切り文字は「,(COMMA U+002C)」が一般的だけど、これは3桁区切りと同じで明治期のお雇いエゲレス人からの借り物でしかない。漢数字だったら中黒つまり「・(U+30FB KATAKANA MIDDLE DOT)」を使うし、アラビア数字であっても縦書きなら中黒とJISも定めておる。

そもそも西欧ですら統一されておらず

桁区切り 小数点 備考
イギリス , (U+002C COMMA) . (U+002E FULL STOP) メシマズ
フランス . (U+002E FULL STOP) , (U+002C COMMA) カエル喰い

と泳いで渡れるドーバー海峡挟んだだけで逆になっとるし、大陸に渡ったメリケン人だと小数点とはすなわち分数の表記法であるとして

3141591145148101919

のように表記したりもしますやね。

@次回予告

次回はこれら国によってまちまちな桁区切りと小数点について、POSIX localeがどのような機能を提供するのかを説明する。

*1:むしろテストコードで使ってるasprintf(3)やopen_memstream(3)って何って言われそうであるが、glibc拡張の前者はともかく後者がPOSIX:2008に入ってもう干支一回りしてるので不勉強悔いてどうぞ。
*2:なお表ではインドの連邦公用語であるヒンディー語かつ代表的な3つの表記法を挙げてあるけど、他にもマラーティー語、ベンガル語、オルドゥ語、タミル語、テルグ語、カンナダ語、マラヤーラム語、ネパール語など、インド憲法で定める22の公用語毎に異なる表記が存在することに注意。
*3:なおカブトボーグの世界ではミリオンは百万でなく1万である、スッゴイカワイソ。
*4:更に後の版では無量大数を 無量 = 1e+68 大数 = 1e+72 としているものもある。
*5:トレイ・ムーア(阪神)が出場した日本シリーズは2003年であって、当発言のあった 2005年の日本シリーズ(33-4)は無関係である、いいね?