INTERNET-DRAFT Adam M. Costello draft-ietf-idn-brace-00.txt 2000-Sep-14 Expires 2001-Mar-14 BRACE: Bi-mode Row-based ASCII-Compatible Encoding for IDN version 0.1.2 Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html Distribution of this document is unlimited. Please send comments to the author at amc@cs.berkeley.edu, or to the idn working group at idn@ops.ietf.org. A newer version of this specification may be available at http://www.cs.berkeley.edu/~amc/charset/brace Abstract BRACE is a reversible function from Unicode (UTF-16) [UNICODE] text strings to host name labels. Host name labels are defined by [RFC952] and [RFC1123] as case-insensitive strings of ASCII letters, digits, and hyphens, neither beginning nor ending with a hyphen. [RFC1034] restricts the length of labels to 63 characters. Contents Primary goals Secondary goals Overview Encoding procedure Base-32 characters Encoding styles Decoding procedure Comparison with RACE Example strings Security considerations References Author Example implementation Primary goals Efficient encoding: Small ratio of encoded size to original size, for all UTF-16 strings. Uniqueness: Every UTF-16 string maps to at most one label. Completeness: Every UTF-16 string maps to a label, provided it is not too long. Restrictions on which UTF-16 strings are allowed is purely a matter of policy. Degeneration: All valid host name labels that do not end with the BRACE signature "-8Q9" (or "-8q9") are the BRACE encodings of their own UTF-16 representations. Secondary goals Conceptual simplicity: This has been somewhat compromised for the sake of efficient encoding. Readability: ASCII letters and digits in the original string are represented literally in the encoded string. This comes for free because it is the most efficient encoding anyway. Overview The encoded string alternates between two modes. ASCII letters, digits, and hyphens in the Unicode string (which will henceforth be called LDH characters) are encoded literally, except that hyphens are doubled. Non-LDH codes in the Unicode string are encoded using base-32 mode, in which each character of the encoded string represents five bits. Single hyphens in the encoded string indicate mode changes. The base-32 mode uses exactly one of four styles. Half-row style is used for Unicode strings in which all the non-LDH codes belong to a single half-row (have the same upper 9 bits). Full-row style is used for Unicode strings in which all the non-LDH codes belong to a single row (have the same upper 8 bits) but not all the same half. Mixed style is used when when many of the non-LDH characters (but not all of them) belong to the same row. No-row style is used for all other strings. Encoding procedure If the UTF-16 string contains more than 63 16-bit codes, it's too long, so abort. If the upper bytes are all zero, and the string formed by the lower bytes is a valid host name label and does not end with "-8Q9" or "-8q9", output the low bytes and stop. The encoder needs a bit queue capable of holding up to 22 bits, a buffer of LDH characters capable of holding up to 124 characters, and a 4-value encoding style indicator. The LDH buffer is initially empty. The initial contents of the bit queue, and the value of the style indicator, depend on which encoding style is chosen (which is explained below). Bit strings are enqueued and dequeued in big-endian order (most significant bit first). After choosing the style and initializing the bit queue, perform the following actions: while the bit queue contains at least 5 bits dequeue 5 bits output the corresponding base-32 character endwhile for each 16-bit code of the UTF-16 string (in order) do if the code is 0x002D ("-", ASCII hyphen) then append two hyphens to the ASCII buffer else if the code is an LDH character then if the LDH buffer contains no non-hyphens then append one hyphen to the LDH buffer endif append the code to the LDH buffer else (the code is not an LDH character) if the LDH buffer contains any non-hyphens then append one hyphen to the LDH buffer endif if the bit queue is empty then output the LDH buffer and reset it to empty endif enqueue the bit string corresponding to the code (the bit string depends on the encoding style) dequeue 5 bits output the corresponding base-32 character output the LDH buffer and reset it to empty while the bit queue contains at least 5 bits dequeue 5 bits output the corresponding base-32 character endwhile endif endfor if the bit queue is not empty enqueue zero bits until it contains 5 bits dequeue 5 bits output the corresponding base-32 character endif output the LDH buffer output the LDH characters "-8Q9" If the total number of characters output was greater than 63, the string is too long for a host name label. Notice that a group of LDH characters appears in the output as soon as all the bits of the preceeding non-LDH codes have appeared. The base-32 character that appears just before the switch to literal mode may contain at most four bits of information from the first non-LDH character that comes after the LDH group. Base-32 characters "2" = 0 = 00000 "3" = 1 = 00001 "4" = 2 = 00010 "5" = 3 = 00011 "6" = 4 = 00100 "7" = 5 = 00101 "8" = 6 = 00110 "9" = 7 = 00111 "A" = 8 = 01000 "B" = 9 = 01001 "C" = 10 = 01010 "D" = 11 = 01011 "E" = 12 = 01100 "F" = 13 = 01101 "G" = 14 = 01110 "H" = 15 = 01111 "I" = 16 = 10000 "J" = 17 = 10001 "K" = 18 = 10010 "M" = 19 = 10011 "N" = 20 = 10100 "P" = 21 = 10101 "Q" = 22 = 10110 "R" = 23 = 10111 "S" = 24 = 11000 "T" = 25 = 11001 "U" = 26 = 11010 "V" = 27 = 11011 "W" = 28 = 11100 "X" = 29 = 11101 "Y" = 30 = 11110 "Z" = 31 = 11111 The digits "0" and "1" and the letters "O" and "L" ("l") are not used, to avoid transcription errors. The base-32 characters, like all characters in host name labels, are case-insensitive, so they must be recognized in both upper and lower case. However, since existing LDH labels are usually stored in lower case, it is recommended that the base-32 portions of encoded names be stored in upper case, to help humans easily pick out the literal portions. Encoding styles The choice of encoding style depends only on the codes in the UTF-16 string that are not LDH characters. It in no way depends on any LDH codes that may be present. Each code belongs to a particular half-row, which is given by its upper 9 bits. If all of the non-LDH codes belong to the same half-row, use half-row style: Initialize the bit queue by enqueuing two 0 bits followed by the designated half-row number (the 9-bit half-row number shared by all the codes). During the encoding procedure the bit string corresponding to each code is its lower 7 bits. If not all the non-LDH codes belong to the same half-row, but they all belong to the same row (same upper 8 bits), use full-row style: Initialize the bit queue by enqueuing a 0 bit, then a 1 bit, then the designated row number (the 8-bit row number shared by all the codes). During the encoding procedure the bit string corresponding to each code is its lower 8 bits. If not all non-LDH codes belong to the same row, then consider using mixed style, which chooses a priviledged half-row. For each half-row used by the non-LDH codes, count the number of codes that belong to that half-row. Then, for each half-row, calculate M, the number of base-32 characters that would be required if that half row were chosen: N = total number of non-LDH codes H = number of non-LDH codes in the candidate half-row C = number of non-LDH codes in the complementary half-row (the one with the opposite lowest bit) M = (2 + 9 + 18*(N - H - C) + 8*H + 9*C + 4) / 5 = 3 + (18*N - 10*H - 9*C) / 5 (The division is integer division, which discards any remainder.) Choose the half-row with the smallest M, breaking ties in favor of lower-numbered half-rows. Compare this M with M', the number of base-32 characters that would be required if no-row style were used: M' = (2 + 16*N + 4) / 5 = (6 + 16*N) / 5 If M' <= M, use no-row style: Initialize the bit queue by enqueueing two 1 bits. There is no designated row number. During the encoding procedure the bit string corresponding to each code is the full 16-bit code itself. If M < M', use mixed style: Initialize the bit queue by enqueueing a 1 bit, then a 0 bit, then the designated 9-bit half-row number (the one chosen above). During the encoding procedure the bit string corresponding to each code is: 0 followed by the lower 7 bits if the code belongs to the chosen half-row; 10 followed by the lower 7 bits if the code belongs to the complementary half-row; 11 followed by the whole 16-bit code otherwise. Decoding procedure The following description assumes that UTF-16 output is desired. If the input string does not end with "-8Q9" or "-8q9", output the input string (converted from ASCII to UTF-16) and stop. The decoder needs a bit queue capable of holding up to 22 bits. It is initially empty. It also needs a literal-mode flag, which is initially unset, and a 4-value style indicator. Perform the following actions: read the first character and enqueue its base-32 quintet dequeue two bits and use them to set the style indicator if the style uses a designated full/half row number then while the queue does not contain enough bits to represent it read the next character and enqueue its base-32 endwhile dequeue enough bits to set the designated row (or half-row) endif for each remaining input character except the last four do if the character is an ASCII hyphen then if the next character is also an ASCII hyphen then skip it output an ASCII hyphen (converted to UTF-16) else toggle the literal-mode flag endif else if the literal-mode flag is set then output the character (converted to UTF-16) else (the literal-mode flag is clear) enqueue the character's base-32 quintet if the bit queue contains enough bits to represent a UTF-16 code (which depends on the style indicator) then dequeue just enough bits to represent one code output the code endif endif endfor At the end the bit queue may contain up to four 0 bits. If it contains anything else, the input was invalid. Comparison with RACE BRACE is an extension of RACE [RACE01]. For Unicode strings that contain no LDH characters and use the full-row or no-row encoding styles, BRACE is virtually identical to RACE. For other strings, BRACE produces a smaller encoding than RACE. For example, the encoding is substantially more compact for Unicode strings containing a substantial number of LDH characters, or containing many Japanese kana with some kanji. Unlike RACE, any LDH characters present in the Unicode string are represented literally in the BRACE-encoded string. This may or may not be useful, but it happens to be the most compact way to encode LDH characters. Whereas RACE uses a signature prefix, BRACE uses a signature suffix. This makes it easy to guarantee that the encoded label never ends with a hyphen, even if the original UTF-16 string does. (Whether such a UTF-16 string should be allowed is a matter of policy, not technical capability). The main drawback of BRACE is its greater complexity. Example strings All of these examples use Japanese text, merely because that is the only kind of non-English text that the author has lying around. Example of no-row style: An actual music group name coerced into the usual format for host name labels: AMURONAMIE-with-super-monkeys AMURONAMIE stands for five kanji whose Unicode values are (in order): U+5B89 U+5BA4 U+5948 U+7F8E U+6075 The BRACE encoding is: UVJ7FUAQCAHY982XA---with--super--monkeys-8Q9 (Note that the RACE encoding would have been 79 characters long, and hence unusable.) Example of mixed style: An actual song title coerced into the usual format for host name labels: hello-another-way-SOREZORENOBASHO SOREZORENOBASHO stands for five hiragana followed by two kanji, whose Unicode values are (in order): U+305D U+308C U+305E U+308C U+306E U+5834 U+6240 The BRACE encoding is: JI7-hello--another--way---V3JHAEFVD2UFJ62-8Q9 Example of full-row style: An actual song title, SONOSUPIIDODE, which stands for two hiragana followed by four katakana followed by one hiragana, whose Unicode values are: U+305D U+306E U+30B9 U+30D4 U+30FC U+30C9 U+3067 The BRACE encoding is: BIDPRDMP9WT7MI-8Q9 Example of half-row style: An actual song title: PAFIIdeRUNBA PAFII stands for four katakana whose Unicode values are: U+30D1 U+30D5 U+30A3 U+30FC RUNBA stands for three katakana whose Unicode values are: U+30EB U+30F3 U+30D0 The BRACE encoding is: 3IU8PAZT-de-PYGI-8Q9 Example of an ASCII string that breaks all the rules of host name labels: -> $1.00 <- The BRACE encoding is: 229--T2B4-1-W-00-I9I---8Q9 Security considerations Users expect each host name in DNS to be controlled by a single authority. If a UTF-16 string could map to multiple labels, then a UTF-16 host name could map to multiple real host names, each controlled by a different authority, some of which could be spoofs that hijack service requests intended for another. Therefore BRACE is designed so that each UTF-16 string maps to a unique label. However, there can still be multiple UTF-16 representations of the "same" text, for various definitions of "same". This problem is addressed by the Unicode standard under the topic of canonicalization, but the issue needs to be studied further in the context of host names. Also, some text strings may be misleading or ambiguous to humans, such as strings containing dots, slashes, at-signs, etc. Policies for allowable Unicode strings need to be developed. References [IDN] Internationalized Domain Names (IETF working group), http://www.i-d-n.net/, idn@ops.ietf.org. [RACE01] Paul Hoffman, "RACE: Row-based ASCII Compatible Encoding for IDN", 2000-Aug-31, draft-ietf-idn-race-01. [RFC952] K. Harrenstien, M. Stahl, E. Feinler, "DOD Internet Host Table Specification", 1985-Oct, RFC 952. [RFC1034] P. Mockapetris, "Domain Names - Concepts and Facilities", 1987-Nov, RFC 1034. [RFC1123] Internet Engineering Task Force, R. Braden (editor), "Requirements for Internet Hosts -- Application and Support", 1989-Oct, RFC 1123. [SACE] Dan Oscarsson, "Simple ASCII Compatible Encoding (SACE)", draft-ietf-idn-sace. [UNICODE] The Unicode Consortium, "The Unicode Standard", http://www.unicode.org/unicode/standard/standard.html. [UTF5] James Seng, Martin Duerst, Tin Wee Tan, "UTF-5, a Transformation Format of Unicode and ISO 10646", draft-jseng-utf5. Author Adam M. Costello http://www.cs.berkeley.edu/~amc/ Example implementation /* brace.c 0.1.1 (2000-Sep-09-Sat) */ /* Adam M. Costello */ /* This is ANSI C code implementing BRACE version 0.1.*. */ /* Public interface (would normally go in its own .h file): */ enum { brace_encoder_in_max = 63, brace_encoder_out_max = 4 + (6 + 16 * brace_encoder_in_max) / 5 + 1, brace_decoder_in_max = 63 + 1, brace_decoder_out_max = brace_decoder_in_max - 1 }; /* The above constants are the maximum array sizes */ /* that the encoder/decoder will accept/produce */ /* (including null terminators for ASCII strings). */ void brace_encode( unsigned int input_length, unsigned short *input, char output[brace_encoder_out_max] ); /* brace_encode() converts UTF-16 input to null-terminated */ /* BRACE-encoded ASCII output. The input_length must not */ /* exceed brace_encoder_in_max, and the output array must */ /* have at least the size indicated below. Under those */ /* constraints, this function never fails. */ int brace_decode( char *input, unsigned int *output_length, unsigned short output[brace_decoder_out_max] ); /* brace_decode() converts null-terminated BRACE-encoded ASCII */ /* input to UTF-16 output. The input length (including the null */ /* terminator) must not exceed brace_encoder_in_max, and output */ /* array must have at least the size indicated below. Returns 1 */ /* on success, 0 if the input was malformed. If 0 is returned */ /* the output array may contain garbage, but *output_length will */ /* not have been affected. */ /* Implementation (would normally go in its own .c file): */ #include static const char base32[] = { 50, 51, 52, 53, 54, 55, 56, 57, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 77, 78, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90 }; /* We can't use string literals for ASCII characters because */ /* an ANSI C compiler does not necessarily use ASCII. */ enum encoding_style { half_row_style = 0, full_row_style = 1, mixed_style = 2, no_row_style = 3 }; /* is_ldh(code) returns 1 if the UTF-16 code represents an LDH */ /* character (ASCII letter, digit, or hyphen), 0 otherwise. */ static int is_ldh(unsigned short code) { if (code == 45) return 1; if (code < 48) return 0; if (code <= 57) return 1; if (code < 65) return 0; if (code <= 90) return 1; if (code < 97) return 0; if (code <= 122) return 1; return 0; } void brace_encode( unsigned int input_length, unsigned short *input, char output[brace_encoder_out_max] ) { unsigned long queue; enum encoding_style style; unsigned short half_rows[brace_encoder_in_max], half_row_counts[brace_encoder_in_max]; unsigned int num_nonldh, num_half_rows, i, half_row, j, queue_length, best_half_row, next_literal_position, non_hyphen_flag, next_base32_position, code; assert(input_length <= brace_encoder_in_max); /* Count the non-LDH codes and half-rows: */ num_nonldh = 0; num_half_rows = 0; for (i = 0; i < input_length; ++i) { if (is_ldh(input[i])) continue; ++num_nonldh; half_row = input[i] >> 7; for (j = 0; j < num_half_rows; ++j) { if (half_rows[j] == half_row) { ++half_row_counts[j]; break; } } if (j == num_half_rows) { half_rows[num_half_rows] = half_row; half_row_counts[num_half_rows] = 1; ++num_half_rows; } } /* If the input is already a valid label and does not end */ /* with the BRACE signature, output it and we're done: */ if (num_nonldh == 0 && /* all codes are LDH and */ input[0] != 45 && /* first not hyphen and */ input[input_length - 1] != 45 && /* last not hyphen and */ !( input[input_length - 1] == 57 && /* last four not -8Q9 */ ( input[input_length - 2] == 81 || input[input_length - 2] == 113 ) && /* (or -8q9) */ input[input_length - 3] == 56 && input[input_length - 4] == 45 ) ) { for (i = 0; i < input_length; ++i) output[i] = input[i]; output[input_length] = 0; /* null terminator */ return; } /* Choose an encoding style and initialize the bit queue: */ if (num_half_rows == 1) { style = half_row_style; queue_length = 11; queue = half_rows[0]; } else if ( num_half_rows == 2 && (half_rows[0] >> 1) == (half_rows[1] >> 1) ) { style = full_row_style; queue_length = 10; queue = (1 << 8) | (half_rows[0] >> 1); } else { unsigned int M, H, C, Mprime, best_M = 230; /* M is always < 230 */ /* Find the best half-row for mixed style: */ best_half_row = 512; /* half_row is always < 512 */ for (i = 0; i < num_half_rows; ++i) { half_row = half_rows[i]; H = half_row_counts[i]; C = 0; for (j = 0; j < num_half_rows; ++j) { if (j != i && (half_rows[j] >> 1) == (half_row >> 1)) { C = half_row_counts[j]; break; } } M = 3 + (18 * num_nonldh - 10*H - 9*C) / 5; if (M < best_M || (M == best_M && half_row < best_half_row)) { best_M = M; best_half_row = half_row; } } /* Compare mixed style to no-row style: */ Mprime = (6 + 16 * num_nonldh) / 5; if (Mprime <= best_M) { style = no_row_style; queue_length = 2; queue = 3; } else { style = mixed_style; queue_length = 11; queue = (1 << 10) | best_half_row; } } /* Flush the bit queue: */ next_base32_position = 0; while (queue_length >= 5) { queue_length -= 5; output[next_base32_position++] = base32[(queue >> queue_length) & 0x1f]; } /* To avoid unnecessary copies, we use the output */ /* array itself for the LDH buffer. The following */ /* equalities should hold whenever the buffer is empty: */ next_literal_position = next_base32_position + (queue_length > 0); non_hyphen_flag = 0; /* set whenever buffer contains a non-hyphen */ /* Main encoding loop: */ for (i = 0; i < input_length; ++i) { code = input[i]; if (code == 45) { /* Encode a hyphen as two hyphens into the buffer: */ output[next_literal_position++] = 45; output[next_literal_position++] = 45; } else if (is_ldh(code)) { if (!non_hyphen_flag) { /* Indicate a change to literal mode: */ output[next_literal_position++] = 45; non_hyphen_flag = 1; } /* Encode the LDH character literally: */ output[next_literal_position++] = code; } else { /* non-LDH code */ if (non_hyphen_flag) { /* Indicate a change to base-32 mode: */ output[next_literal_position++] = 45; non_hyphen_flag = 0; /* we will empty the buffer */ } /* If the bit queue is empty, flush the LDH buffer: */ if (queue_length == 0) { next_base32_position = next_literal_position; } /* Enqueue the bit string corresponding to the code: */ if (style == half_row_style) { queue = (queue << 7) | (code & 0x7f); queue_length += 7; } else if (style == full_row_style) { queue = (queue << 8) | (code & 0xff); queue_length += 8; } else if (style == no_row_style) { queue = (queue << 16) | code; queue_length += 16; } else /* style == mixed_style */ { if ((code >> 7) == best_half_row) { queue = (queue << 8) | (code & 0x7f); queue_length += 8; } else if ((code >> 8) == (best_half_row >> 1)) { queue = (queue << 9) | (1 << 8) | (code & 0x7f); queue_length += 9; } else { queue = (queue << 18) | (3ul << 16) | code; queue_length += 18; } } /* Output one base-32 character: */ queue_length -= 5; output[next_base32_position] = base32[(queue >> queue_length) & 0x1f]; if (next_base32_position == next_literal_position) { /* LDH buffer is already empty. */ ++next_base32_position; } else { /* Flush the LDH buffer: */ next_base32_position = next_literal_position; } /* next_literal_position is momentarily invalid, */ /* but we know the LDH buffer is empty. */ /* Flush the bit queue: */ while (queue_length >= 5) { queue_length -= 5; output[next_base32_position++] = base32[(queue >> queue_length) & 0x1f]; } /* Fix next_literal_position: */ next_literal_position = next_base32_position + (queue_length > 0); } assert(next_literal_position < brace_encoder_out_max); } /* Flush the bit queue: */ if (queue_length > 0) { assert(queue_length < 5); output[next_base32_position] = base32[(queue << (5 - queue_length)) & 0x1f]; } /* Flushing the LDH buffer at this point is a no-op. */ /* Output "-8Q9" and the null terminator: */ assert(next_literal_position + 4 < brace_encoder_out_max); output[next_literal_position++] = 45; output[next_literal_position++] = 56; output[next_literal_position++] = 81; output[next_literal_position++] = 57; output[next_literal_position] = 0; } /* base32_decode() converts a base-32 character to a value from */ /* 0 to 31. If the character is valid, its value is written to */ /* *quintet and 1 is returned. Otherwise, *value is not changed */ /* and 0 is returned. */ static int base32_decode(char c, unsigned int *quintet) { if (c < 50) return 0; if (c <= 57) { *quintet = c - 50; return 1; } if (c < 65) return 0; if (c >= 97) c -= 32; if (c <= 75) { *quintet = c - 57; return 1; } if (c == 76) return 0; if (c <= 78) { *quintet = c - 58; return 1; } if (c == 79) return 0; if (c <= 90) { *quintet = c - 59; return 1; } return 0; } int brace_decode( char *input, unsigned int *output_length, unsigned short output[brace_decoder_out_max] ) { unsigned long queue; unsigned int i, input_length, queue_length, literal_mode_flag, quintet, n, next_code_position; enum encoding_style style; unsigned short common_prefix; char c; /* Check whether input ends with "-8Q9": */ for (i = 0; input[i]; ++i) assert(i < brace_decoder_in_max); if (!(input[i-1] == 57 && input[i-3] == 56 && input[i-4] == 45 && (input[i-2] == 81 || input[i-2] == 113))) { /* Copy input to output and we're done: */ for (i = 0; input[i]; ++i) output[i] = input[i]; assert(i <= brace_decoder_out_max); *output_length = i; return 1; } /* Initialize using the first base-32 character: */ input_length = i; i = 0; if (!base32_decode(input[i], &quintet)) return 0; queue = quintet; queue_length = 3; literal_mode_flag = 0; style = quintet >> 3; /* Determine common_prefix: */ if (style == no_row_style) n = 0; else if (style == full_row_style) n = 8; else n = 9; while (queue_length < n) { if (!base32_decode(input[++i], &quintet)) return 0; queue = (queue << 5) | quintet; queue_length += 5; } common_prefix = (queue >> (queue_length - n)) << (16 - n); queue_length -= n; /* Main decoding loop: */ next_code_position = 0; while (++i < input_length - 4) { c = input[i]; if (c == 45) { if (input[i+1] == 45) { ++i; output[next_code_position++] = 45; /* "--" means "-" */ } else literal_mode_flag ^= 1; /* "-" toggles literal mode */ } else if (literal_mode_flag) { /* literal non-hyphen */ output[next_code_position++] = c; } else { /* base-32 character */ /* Enqueue the corresponding quintet: */ if (!base32_decode(c, &quintet)) return 0; queue = (queue << 5) | quintet; queue_length += 5; /* If the queue contains enough bits for a UTF-16 code, */ /* dequeue them, decode them, and output the code: */ if (style == no_row_style && queue_length >= 16) { output[next_code_position++] = (queue >> (queue_length - 16)) & 0xffff; queue_length -= 16; } else if (style == full_row_style && queue_length >= 8) { output[next_code_position++] = common_prefix | ((queue >> (queue_length - 8)) & 0xff); queue_length -= 8; } else if (style == half_row_style && queue_length >= 7) { output[next_code_position++] = common_prefix | ((queue >> (queue_length - 7)) & 0x7f); queue_length -= 7; } else if (style == mixed_style) { n = (queue >> (queue_length - 2)) & 3; /* top 2 bits */ if (n <= 1 && queue_length >= 8) { output[next_code_position++] = common_prefix | ((queue >> (queue_length - 8)) & 0x7f); queue_length -= 8; } else if (n == 2 && queue_length >= 9) { output[next_code_position++] = (common_prefix ^ 0x80) | ((queue >> (queue_length - 9)) & 0x7f); queue_length -= 9; } else if (n == 3 && queue_length >= 18) { output[next_code_position++] = (queue >> (queue_length - 18)) & 0xffff; queue_length -= 18; } } } } assert(next_code_position <= brace_decoder_out_max); /* Check that the bit queue contains only zeros, at most four: */ if (queue_length > 4) return 0; if ((queue & ((1 << queue_length) - 1)) != 0) return 0; /* Set the output length and we're done: */ *output_length = next_code_position; return 1; } /* Wrapper for testing (would normally go in a separate .c file): */ #include #include #include static void usage(char **argv) { fprintf(stderr, "%s -e reads big-endian UTF-16 and writes BRACE-format ASCII.\n" "%s -d reads BRACE-format ASCII and writes big-endian UTF-16.\n" , argv[0], argv[0]); exit(EXIT_FAILURE); } static void fail(const char *msg) { fputs(msg,stderr); exit(EXIT_FAILURE); } static const char input_too_large[] = "input is too large\n"; int main(int argc, char **argv) { unsigned int input_length; if (argc != 2) usage(argv); if (argv[1][0] != '-') usage(argv); if (argv[1][2] != '\0') usage(argv); if (argv[1][1] == 'e') { unsigned short input[brace_encoder_in_max]; char output[brace_encoder_out_max]; int hi, lo; /* Read the UTF-16 input string: */ input_length = 0; for (;;) { hi = getchar(); lo = getchar(); if (lo == EOF) { if (hi != EOF) fail("input contained an odd number of bytes\n"); break; } if (input_length == brace_encoder_in_max) fail(input_too_large); if (hi > 0xff || lo > 0xff) { fail("input bytes do not fit in 8 bits\n"); } input[input_length++] = (unsigned short) hi << 8 | (unsigned short) lo; } /* Encode, and output the result: */ brace_encode(input_length, input, output); if (strlen(output) > brace_decoder_in_max) fail(input_too_large); fputs(output,stdout); return EXIT_SUCCESS; } if (argv[1][1] == 'd') { char input[brace_decoder_in_max]; unsigned short output[brace_decoder_out_max]; unsigned int output_length, i; size_t n; /* Read the BRACE-encoded ASCII input string: */ n = fread(input, 1, brace_decoder_in_max, stdin); if (n == brace_decoder_in_max) fail(input_too_large); input[n] = 0; /* Decode, and output the result: */ if (!brace_decode(input, &output_length, output)) { fail("input was malformed\n"); } for (i = 0; i < output_length; ++i) { putchar(output[i] >> 8); putchar(output[i] & 0xff); } return EXIT_SUCCESS; } usage(argv); return EXIT_SUCCESS; /* not reached, but quiets compiler warning */ } INTERNET-DRAFT expires 2001-Mar-14