-
Notifications
You must be signed in to change notification settings - Fork 4
/
455.txt
2114 lines (1771 loc) · 69.1 KB
/
455.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
;; [[Punycode]] も参照。
Network Working Group A. Costello
Request for Comments: 3492 Univ. of California, Berkeley
Category: Standards Track March 2003
[PRE[
Punycode: A Bootstring encoding of Unicode
for Internationalized Domain Names in Applications (IDNA)
]PRE]
* Status of this Memo
[PRE[
This document specifies an Internet standards track protocol for the
Internet community, and requests discussion and suggestions for
improvements. Please refer to the current edition of the "Internet
Official Protocol Standards" (STD 1) for the standardization state
and status of this protocol. Distribution of this memo is unlimited.
]PRE]
* Copyright Notice
[PRE[
Copyright (C) The Internet Society (2003). All Rights Reserved.
]PRE]
* Abstract
> Punycode is a simple and efficient transfer encoding syntax designed
for use with Internationalized Domain Names in Applications (IDNA).
It uniquely and reversibly transforms a Unicode string into an ASCII
string. ASCII characters in the Unicode string are represented
literally, and non-ASCII characters are represented by ASCII
characters that are allowed in host name labels (letters, digits, and
hyphens). This document defines a general algorithm called
Bootstring that allows a string of basic code points to uniquely
represent any string of code points drawn from a larger set.
Punycode is an instance of Bootstring that uses particular parameter
values specified by this document, appropriate for IDNA.
[[Punycode]] は、[[応用国際化ドメイン名]] ([[IDNA]])
で使うために設計された、単純で効率的な転送符号化構文です。
[[Punycode]] は、固有かつ可逆に [[Unicode]]
[[文字列]]を [[ASCII]] [[文字列]]に変形します。
[[Unicode]] [[文字列]]中の [[ASCII]] [[文字]]はそのまま表現され、
[[非ASCII文字]]は[[ホスト名札]]で認められている [[ASCII]] [[文字]]
([[ラテン文字]]、[[数字]]、[[ハイフン]]) で表現します。
この文書は、 [[Bootstring]] という、
[[基本符号位置]]の[[文字列]]により、
より大きな集合の[[符号位置]]の任意の[[文字列]]を固有に表現するための一般的な[[算法]]を定義します。
[[Punycode]] は、この文書で規定する特定の[[引数値]]を用いた [[Bootstring]]
の[[実現値]]で、 [[IDNA]] に適しています。
* Table of Contents
[PRE[
1. Introduction...............................................2
1.1 Features..............................................2
1.2 Interaction of protocol parts.........................3
2. Terminology................................................3
3. Bootstring description.....................................4
3.1 Basic code point segregation..........................4
3.2 Insertion unsort coding...............................4
3.3 Generalized variable-length integers..................5
3.4 Bias adaptation.......................................7
4. Bootstring parameters......................................8
5. Parameter values for Punycode..............................8
6. Bootstring algorithms......................................9
6.1 Bias adaptation function.............................10
6.2 Decoding procedure...................................11
6.3 Encoding procedure...................................12
6.4 Overflow handling....................................13
7. Punycode examples.........................................14
7.1 Sample strings.......................................14
7.2 Decoding traces......................................17
7.3 Encoding traces......................................19
8. Security Considerations...................................20
9. References................................................21
9.1 Normative References.................................21
9.2 Informative References...............................21
A. Mixed-case annotation.....................................22
B. Disclaimer and license....................................22
C. Punycode sample implementation............................23
Author's Address.............................................34
Full Copyright Statement.....................................35
]PRE]
* 1. Introduction
[PRE[
[IDNA] describes an architecture for supporting internationalized
domain names. Labels containing non-ASCII characters can be
represented by ACE labels, which begin with a special ACE prefix and
contain only ASCII characters. The remainder of the label after the
prefix is a Punycode encoding of a Unicode string satisfying certain
constraints. For the details of the prefix and constraints, see
[IDNA] and [NAMEPREP].
]PRE]
[PRE[
Punycode is an instance of a more general algorithm called
Bootstring, which allows strings composed from a small set of "basic"
code points to uniquely represent any string of code points drawn
from a larger set. Punycode is Bootstring with particular parameter
values appropriate for IDNA.
]PRE]
** 1.1 Features
[PRE[
Bootstring has been designed to have the following features:
]PRE]
[PRE[
* Completeness: Every extended string (sequence of arbitrary code
points) can be represented by a basic string (sequence of basic
code points). Restrictions on what strings are allowed, and on
length, can be imposed by higher layers.
]PRE]
[PRE[
* Uniqueness: There is at most one basic string that represents a
given extended string.
]PRE]
[PRE[
* Reversibility: Any extended string mapped to a basic string can
be recovered from that basic string.
]PRE]
[PRE[
* Efficient encoding: The ratio of basic string length to extended
string length is small. This is important in the context of
domain names because RFC 1034 [RFC1034] restricts the length of a
domain label to 63 characters.
]PRE]
[PRE[
* Simplicity: The encoding and decoding algorithms are reasonably
simple to implement. The goals of efficiency and simplicity are
at odds; Bootstring aims at a good balance between them.
]PRE]
[PRE[
* Readability: Basic code points appearing in the extended string
are represented as themselves in the basic string (although the
main purpose is to improve efficiency, not readability).
]PRE]
[PRE[
Punycode can also support an additional feature that is not used by
the ToASCII and ToUnicode operations of [IDNA]. When extended
strings are case-folded prior to encoding, the basic string can use
mixed case to tell how to convert the folded string into a mixed-case
string. See appendix A "Mixed-case annotation".
]PRE]
** 1.2 Interaction of protocol parts
[PRE[
Punycode is used by the IDNA protocol [IDNA] for converting domain
labels into ASCII; it is not designed for any other purpose. It is
explicitly not designed for processing arbitrary free text.
]PRE]
* 2. Terminology
[PRE[
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in BCP 14, RFC 2119
[RFC2119].
]PRE]
[PRE[
A code point is an integral value associated with a character in a
coded character set.
]PRE]
[PRE[
As in the Unicode Standard [UNICODE], Unicode code points are denoted
by "U+" followed by four to six hexadecimal digits, while a range of
code points is denoted by two hexadecimal numbers separated by "..",
with no prefixes.
]PRE]
[PRE[
The operators div and mod perform integer division; (x div y) is the
quotient of x divided by y, discarding the remainder, and (x mod y)
is the remainder, so (x div y) * y + (x mod y) == x. Bootstring uses
these operators only with nonnegative operands, so the quotient and
remainder are always nonnegative.
]PRE]
[PRE[
The break statement jumps out of the innermost loop (as in C).
]PRE]
[PRE[
An overflow is an attempt to compute a value that exceeds the maximum
value of an integer variable.
]PRE]
* 3. Bootstring description
[PRE[
Bootstring represents an arbitrary sequence of code points (the
"extended string") as a sequence of basic code points (the "basic
string"). This section describes the representation. Section 6
"Bootstring algorithms" presents the algorithms as pseudocode.
Sections 7.1 "Decoding traces" and 7.2 "Encoding traces" trace the
algorithms for sample inputs.
]PRE]
[PRE[
The following sections describe the four techniques used in
Bootstring. "Basic code point segregation" is a very simple and
efficient encoding for basic code points occurring in the extended
string: they are simply copied all at once. "Insertion unsort
coding" encodes the non-basic code points as deltas, and processes
the code points in numerical order rather than in order of
appearance, which typically results in smaller deltas. The deltas
are represented as "generalized variable-length integers", which use
basic code points to represent nonnegative integers. The parameters
of this integer representation are dynamically adjusted using "bias
adaptation", to improve efficiency when consecutive deltas have
similar magnitudes.
]PRE]
3.1 Basic code point segregation
[PRE[
All basic code points appearing in the extended string are
represented literally at the beginning of the basic string, in their
original order, followed by a delimiter if (and only if) the number
of basic code points is nonzero. The delimiter is a particular basic
code point, which never appears in the remainder of the basic string.
The decoder can therefore find the end of the literal portion (if
there is one) by scanning for the last delimiter.
]PRE]
3.2 Insertion unsort coding
[PRE[
The remainder of the basic string (after the last delimiter if there
is one) represents a sequence of nonnegative integral deltas as
generalized variable-length integers, described in section 3.3. The
meaning of the deltas is best understood in terms of the decoder.
]PRE]
[PRE[
The decoder builds the extended string incrementally. Initially, the
extended string is a copy of the literal portion of the basic string
(excluding the last delimiter). The decoder inserts non-basic code
points, one for each delta, into the extended string, ultimately
arriving at the final decoded string.
]PRE]
Costello Standards Track [Page 4]
[PRE[
RFC 3492 IDNA Punycode March 2003
]PRE]
[PRE[
At the heart of this process is a state machine with two state
variables: an index i and a counter n. The index i refers to a
position in the extended string; it ranges from 0 (the first
position) to the current length of the extended string (which refers
to a potential position beyond the current end). If the current
state is <n,i>, the next state is <n,i+1> if i is less than the
length of the extended string, or <n+1,0> if i equals the length of
the extended string. In other words, each state change causes i to
increment, wrapping around to zero if necessary, and n counts the
number of wrap-arounds.
]PRE]
[PRE[
Notice that the state always advances monotonically (there is no way
for the decoder to return to an earlier state). At each state, an
insertion is either performed or not performed. At most one
insertion is performed in a given state. An insertion inserts the
value of n at position i in the extended string. The deltas are a
run-length encoding of this sequence of events: they are the lengths
of the runs of non-insertion states preceeding the insertion states.
Hence, for each delta, the decoder performs delta state changes, then
an insertion, and then one more state change. (An implementation
need not perform each state change individually, but can instead use
division and remainder calculations to compute the next insertion
state directly.) It is an error if the inserted code point is a
basic code point (because basic code points were supposed to be
segregated as described in section 3.1).
]PRE]
[PRE[
The encoder's main task is to derive the sequence of deltas that will
cause the decoder to construct the desired string. It can do this by
repeatedly scanning the extended string for the next code point that
the decoder would need to insert, and counting the number of state
changes the decoder would need to perform, mindful of the fact that
the decoder's extended string will include only those code points
that have already been inserted. Section 6.3 "Encoding procedure"
gives a precise algorithm.
]PRE]
3.3 Generalized variable-length integers
[PRE[
In a conventional integer representation the base is the number of
distinct symbols for digits, whose values are 0 through base-1. Let
digit_0 denote the least significant digit, digit_1 the next least
significant, and so on. The value represented is the sum over j of
digit_j * w(j), where w(j) = base^j is the weight (scale factor) for
position j. For example, in the base 8 integer 437, the digits are
7, 3, and 4, and the weights are 1, 8, and 64, so the value is 7 +
3*8 + 4*64 = 287. This representation has two disadvantages: First,
there are multiple encodings of each value (because there can be
extra zeros in the most significant positions), which is inconvenient
]PRE]
Costello Standards Track [Page 5]
[PRE[
RFC 3492 IDNA Punycode March 2003
]PRE]
[PRE[
when unique encodings are needed. Second, the integer is not self-
delimiting, so if multiple integers are concatenated the boundaries
between them are lost.
]PRE]
[PRE[
The generalized variable-length representation solves these two
problems. The digit values are still 0 through base-1, but now the
integer is self-delimiting by means of thresholds t(j), each of which
is in the range 0 through base-1. Exactly one digit, the most
significant, satisfies digit_j < t(j). Therefore, if several
integers are concatenated, it is easy to separate them, starting with
the first if they are little-endian (least significant digit first),
or starting with the last if they are big-endian (most significant
digit first). As before, the value is the sum over j of digit_j *
w(j), but the weights are different:
]PRE]
[PRE[
w(0) = 1
w(j) = w(j-1) * (base - t(j-1)) for j > 0
]PRE]
[PRE[
For example, consider the little-endian sequence of base 8 digits
734251... Suppose the thresholds are 2, 3, 5, 5, 5, 5... This
implies that the weights are 1, 1*(8-2) = 6, 6*(8-3) = 30, 30*(8-5) =
90, 90*(8-5) = 270, and so on. 7 is not less than 2, and 3 is not
less than 3, but 4 is less than 5, so 4 is the last digit. The value
of 734 is 7*1 + 3*6 + 4*30 = 145. The next integer is 251, with
value 2*1 + 5*6 + 1*30 = 62. Decoding this representation is very
similar to decoding a conventional integer: Start with a current
value of N = 0 and a weight w = 1. Fetch the next digit d and
increase N by d * w. If d is less than the current threshold (t)
then stop, otherwise increase w by a factor of (base - t), update t
for the next position, and repeat.
]PRE]
[PRE[
Encoding this representation is similar to encoding a conventional
integer: If N < t then output one digit for N and stop, otherwise
output the digit for t + ((N - t) mod (base - t)), then replace N
with (N - t) div (base - t), update t for the next position, and
repeat.
]PRE]
[PRE[
For any particular set of values of t(j), there is exactly one
generalized variable-length representation of each nonnegative
integral value.
]PRE]
[PRE[
Bootstring uses little-endian ordering so that the deltas can be
separated starting with the first. The t(j) values are defined in
terms of the constants base, tmin, and tmax, and a state variable
called bias:
]PRE]
[PRE[
t(j) = base * (j + 1) - bias,
clamped to the range tmin through tmax
]PRE]
Costello Standards Track [Page 6]
[PRE[
RFC 3492 IDNA Punycode March 2003
]PRE]
[PRE[
The clamping means that if the formula yields a value less than tmin
or greater than tmax, then t(j) = tmin or tmax, respectively. (In
the pseudocode in section 6 "Bootstring algorithms", the expression
base * (j + 1) is denoted by k for performance reasons.) These t(j)
values cause the representation to favor integers within a particular
range determined by the bias.
]PRE]
3.4 Bias adaptation
[PRE[
After each delta is encoded or decoded, bias is set for the next
delta as follows:
]PRE]
[PRE[
1. Delta is scaled in order to avoid overflow in the next step:
]PRE]
[PRE[
let delta = delta div 2
]PRE]
[PRE[
But when this is the very first delta, the divisor is not 2, but
instead a constant called damp. This compensates for the fact
that the second delta is usually much smaller than the first.
]PRE]
[PRE[
2. Delta is increased to compensate for the fact that the next delta
will be inserting into a longer string:
]PRE]
[PRE[
let delta = delta + (delta div numpoints)
]PRE]
[PRE[
numpoints is the total number of code points encoded/decoded so
far (including the one corresponding to this delta itself, and
including the basic code points).
]PRE]
[PRE[
3. Delta is repeatedly divided until it falls within a threshold, to
predict the minimum number of digits needed to represent the next
delta:
]PRE]
[PRE[
while delta > ((base - tmin) * tmax) div 2
do let delta = delta div (base - tmin)
]PRE]
[PRE[
4. The bias is set:
]PRE]
[PRE[
let bias =
(base * the number of divisions performed in step 3) +
(((base - tmin + 1) * delta) div (delta + skew))
]PRE]
[PRE[
The motivation for this procedure is that the current delta
provides a hint about the likely size of the next delta, and so
t(j) is set to tmax for the more significant digits starting with
the one expected to be last, tmin for the less significant digits
up through the one expected to be third-last, and somewhere
between tmin and tmax for the digit expected to be second-last
]PRE]
Costello Standards Track [Page 7]
[PRE[
RFC 3492 IDNA Punycode March 2003
]PRE]
[PRE[
(balancing the hope of the expected-last digit being unnecessary
against the danger of it being insufficient).
]PRE]
4. Bootstring parameters
[PRE[
Given a set of basic code points, one needs to be designated as the
delimiter. The base cannot be greater than the number of
distinguishable basic code points remaining. The digit-values in the
range 0 through base-1 need to be associated with distinct non-
delimiter basic code points. In some cases multiple code points need
to have the same digit-value; for example, uppercase and lowercase
versions of the same letter need to be equivalent if basic strings
are case-insensitive.
]PRE]
[PRE[
The initial value of n cannot be greater than the minimum non-basic
code point that could appear in extended strings.
]PRE]
[PRE[
The remaining five parameters (tmin, tmax, skew, damp, and the
initial value of bias) need to satisfy the following constraints:
]PRE]
[PRE[
0 <= tmin <= tmax <= base-1
skew >= 1
damp >= 2
initial_bias mod base <= base - tmin
]PRE]
[PRE[
Provided the constraints are satisfied, these five parameters affect
efficiency but not correctness. They are best chosen empirically.
]PRE]
[PRE[
If support for mixed-case annotation is desired (see appendix A),
make sure that the code points corresponding to 0 through tmax-1 all
have both uppercase and lowercase forms.
]PRE]
5. Parameter values for Punycode
[PRE[
Punycode uses the following Bootstring parameter values:
]PRE]
[PRE[
base = 36
tmin = 1
tmax = 26
skew = 38
damp = 700
initial_bias = 72
initial_n = 128 = 0x80
]PRE]
[PRE[
Although the only restriction Punycode imposes on the input integers
is that they be nonnegative, these parameters are especially designed
to work well with Unicode [UNICODE] code points, which are integers
in the range 0..10FFFF (but not D800..DFFF, which are reserved for
]PRE]
Costello Standards Track [Page 8]
[PRE[
RFC 3492 IDNA Punycode March 2003
]PRE]
[PRE[
use by the UTF-16 encoding of Unicode). The basic code points are
the ASCII [ASCII] code points (0..7F), of which U+002D (-) is the
delimiter, and some of the others have digit-values as follows:
]PRE]
[PRE[
code points digit-values
------------ ----------------------
41..5A (A-Z) = 0 to 25, respectively
61..7A (a-z) = 0 to 25, respectively
30..39 (0-9) = 26 to 35, respectively
]PRE]
[PRE[
Using hyphen-minus as the delimiter implies that the encoded string
can end with a hyphen-minus only if the Unicode string consists
entirely of basic code points, but IDNA forbids such strings from
being encoded. The encoded string can begin with a hyphen-minus, but
IDNA prepends a prefix. Therefore IDNA using Punycode conforms to
the RFC 952 rule that host name labels neither begin nor end with a
hyphen-minus [RFC952].
]PRE]
[PRE[
A decoder MUST recognize the letters in both uppercase and lowercase
forms (including mixtures of both forms). An encoder SHOULD output
only uppercase forms or only lowercase forms, unless it uses mixed-
case annotation (see appendix A).
]PRE]
[PRE[
Presumably most users will not manually write or type encoded strings
(as opposed to cutting and pasting them), but those who do will need
to be alert to the potential visual ambiguity between the following
sets of characters:
]PRE]
[PRE[
G 6
I l 1
O 0
S 5
U V
Z 2
]PRE]
[PRE[
Such ambiguities are usually resolved by context, but in a Punycode
encoded string there is no context apparent to humans.
]PRE]
6. Bootstring algorithms
[PRE[
Some parts of the pseudocode can be omitted if the parameters satisfy
certain conditions (for which Punycode qualifies). These parts are
enclosed in {braces}, and notes immediately following the pseudocode
explain the conditions under which they can be omitted.
]PRE]
Costello Standards Track [Page 9]
[PRE[
RFC 3492 IDNA Punycode March 2003
]PRE]
[PRE[
Formally, code points are integers, and hence the pseudocode assumes
that arithmetic operations can be performed directly on code points.
In some programming languages, explicit conversion between code
points and integers might be necessary.
]PRE]
6.1 Bias adaptation function
[PRE[
function adapt(delta,numpoints,firsttime):
if firsttime then let delta = delta div damp
else let delta = delta div 2
let delta = delta + (delta div numpoints)
let k = 0
while delta > ((base - tmin) * tmax) div 2 do begin
let delta = delta div (base - tmin)
let k = k + base
end
return k + (((base - tmin + 1) * delta) div (delta + skew))
]PRE]
[PRE[
It does not matter whether the modifications to delta and k inside
adapt() affect variables of the same name inside the
encoding/decoding procedures, because after calling adapt() the
caller does not read those variables before overwriting them.
]PRE]
Costello Standards Track [Page 10]
[PRE[
RFC 3492 IDNA Punycode March 2003
]PRE]
6.2 Decoding procedure
[PRE[
let n = initial_n
let i = 0
let bias = initial_bias
let output = an empty string indexed from 0
consume all code points before the last delimiter (if there is one)
and copy them to output, fail on any non-basic code point
if more than zero code points were consumed then consume one more
(which will be the last delimiter)
while the input is not exhausted do begin
let oldi = i
let w = 1
for k = base to infinity in steps of base do begin
consume a code point, or fail if there was none to consume
let digit = the code point's digit-value, fail if it has none
let i = i + digit * w, fail on overflow
let t = tmin if k <= bias {+ tmin}, or
tmax if k >= bias + tmax, or k - bias otherwise
if digit < t then break
let w = w * (base - t), fail on overflow
end
let bias = adapt(i - oldi, length(output) + 1, test oldi is 0?)
let n = n + i div (length(output) + 1), fail on overflow
let i = i mod (length(output) + 1)
{if n is a basic code point then fail}
insert n into output at position i
increment i
end
]PRE]
[PRE[
The full statement enclosed in braces (checking whether n is a basic
code point) can be omitted if initial_n exceeds all basic code points
(which is true for Punycode), because n is never less than initial_n.
]PRE]
[PRE[
In the assignment of t, where t is clamped to the range tmin through
tmax, "+ tmin" can always be omitted. This makes the clamping
calculation incorrect when bias < k < bias + tmin, but that cannot
happen because of the way bias is computed and because of the
constraints on the parameters.
]PRE]
[PRE[
Because the decoder state can only advance monotonically, and there
is only one representation of any delta, there is therefore only one
encoded string that can represent a given sequence of integers. The
only error conditions are invalid code points, unexpected end-of-
input, overflow, and basic code points encoded using deltas instead
of appearing literally. If the decoder fails on these errors as
shown above, then it cannot produce the same output for two distinct
inputs. Without this property it would have been necessary to re-
]PRE]
Costello Standards Track [Page 11]
[PRE[
RFC 3492 IDNA Punycode March 2003
]PRE]
[PRE[
encode the output and verify that it matches the input in order to
guarantee the uniqueness of the encoding.
]PRE]
6.3 Encoding procedure
[PRE[
let n = initial_n
let delta = 0
let bias = initial_bias
let h = b = the number of basic code points in the input
copy them to the output in order, followed by a delimiter if b > 0
{if the input contains a non-basic code point < n then fail}
while h < length(input) do begin
let m = the minimum {non-basic} code point >= n in the input
let delta = delta + (m - n) * (h + 1), fail on overflow
let n = m
for each code point c in the input (in order) do begin
if c < n {or c is basic} then increment delta, fail on overflow
if c == n then begin
let q = delta
for k = base to infinity in steps of base do begin
let t = tmin if k <= bias {+ tmin}, or
tmax if k >= bias + tmax, or k - bias otherwise
if q < t then break
output the code point for digit t + ((q - t) mod (base - t))
let q = (q - t) div (base - t)
end
output the code point for digit q
let bias = adapt(delta, h + 1, test h equals b?)
let delta = 0
increment h
end
end
increment delta and n
end
]PRE]
[PRE[
The full statement enclosed in braces (checking whether the input
contains a non-basic code point less than n) can be omitted if all
code points less than initial_n are basic code points (which is true
for Punycode if code points are unsigned).
]PRE]
[PRE[
The brace-enclosed conditions "non-basic" and "or c is basic" can be
omitted if initial_n exceeds all basic code points (which is true for
Punycode), because the code point being tested is never less than
initial_n.
]PRE]
[PRE[
In the assignment of t, where t is clamped to the range tmin through
tmax, "+ tmin" can always be omitted. This makes the clamping
calculation incorrect when bias < k < bias + tmin, but that cannot
]PRE]
Costello Standards Track [Page 12]
[PRE[
RFC 3492 IDNA Punycode March 2003
]PRE]
[PRE[
happen because of the way bias is computed and because of the
constraints on the parameters.
]PRE]
[PRE[
The checks for overflow are necessary to avoid producing invalid
output when the input contains very large values or is very long.
]PRE]
[PRE[
The increment of delta at the bottom of the outer loop cannot
overflow because delta < length(input) before the increment, and
length(input) is already assumed to be representable. The increment
of n could overflow, but only if h == length(input), in which case
the procedure is finished anyway.
]PRE]
6.4 Overflow handling
[PRE[
For IDNA, 26-bit unsigned integers are sufficient to handle all valid
IDNA labels without overflow, because any string that needed a 27-bit
delta would have to exceed either the code point limit (0..10FFFF) or
the label length limit (63 characters). However, overflow handling
is necessary because the inputs are not necessarily valid IDNA
labels.
]PRE]
[PRE[
If the programming language does not provide overflow detection, the
following technique can be used. Suppose A, B, and C are
representable nonnegative integers and C is nonzero. Then A + B
overflows if and only if B > maxint - A, and A + (B * C) overflows if
and only if B > (maxint - A) div C, where maxint is the greatest
integer for which maxint + 1 cannot be represented. Refer to
appendix C "Punycode sample implementation" for demonstrations of
this technique in the C language.
]PRE]
[PRE[
The decoding and encoding algorithms shown in sections 6.2 and 6.3
handle overflow by detecting it whenever it happens. Another
approach is to enforce limits on the inputs that prevent overflow
from happening. For example, if the encoder were to verify that no
input code points exceed M and that the input length does not exceed
L, then no delta could ever exceed (M - initial_n) * (L + 1), and
hence no overflow could occur if integer variables were capable of
representing values that large. This prevention approach would
impose more restrictions on the input than the detection approach
does, but might be considered simpler in some programming languages.
]PRE]
[PRE[
In theory, the decoder could use an analogous approach, limiting the
number of digits in a variable-length integer (that is, limiting the
number of iterations in the innermost loop). However, the number of
digits that suffice to represent a given delta can sometimes
represent much larger deltas (because of the adaptation), and hence
this approach would probably need integers wider than 32 bits.
]PRE]
Costello Standards Track [Page 13]
[PRE[
RFC 3492 IDNA Punycode March 2003
]PRE]
[PRE[
Yet another approach for the decoder is to allow overflow to occur,
but to check the final output string by re-encoding it and comparing
to the decoder input. If and only if they do not match (using a
case-insensitive ASCII comparison) overflow has occurred. This
delayed-detection approach would not impose any more restrictions on
the input than the immediate-detection approach does, and might be
considered simpler in some programming languages.
]PRE]
[PRE[
In fact, if the decoder is used only inside the IDNA ToUnicode
operation [IDNA], then it need not check for overflow at all, because
ToUnicode performs a higher level re-encoding and comparison, and a
mismatch has the same consequence as if the Punycode decoder had
failed.
]PRE]
7. Punycode examples
7.1 Sample strings
[PRE[
In the Punycode encodings below, the ACE prefix is not shown.
Backslashes show where line breaks have been inserted in strings too
long for one line.
]PRE]
[PRE[
The first several examples are all translations of the sentence "Why
can't they just speak in <language>?" (courtesy of Michael Kaplan's
"provincial" page [PROVINCIAL]). Word breaks and punctuation have
been removed, as is often done in domain names.
]PRE]
[PRE[
(A) Arabic (Egyptian):
u+0644 u+064A u+0647 u+0645 u+0627 u+0628 u+062A u+0643 u+0644
u+0645 u+0648 u+0634 u+0639 u+0631 u+0628 u+064A u+061F
Punycode: egbpdaj6bu4bxfgehfvwxn
]PRE]
[PRE[
(B) Chinese (simplified):
u+4ED6 u+4EEC u+4E3A u+4EC0 u+4E48 u+4E0D u+8BF4 u+4E2D u+6587
Punycode: ihqwcrb4cv8a8dqg056pqjye
]PRE]
[PRE[
(C) Chinese (traditional):
u+4ED6 u+5011 u+7232 u+4EC0 u+9EBD u+4E0D u+8AAA u+4E2D u+6587
Punycode: ihqwctvzc91f659drss3x8bo0yb
]PRE]
[PRE[
(D) Czech: Pro<ccaron>prost<ecaron>nemluv<iacute><ccaron>esky
U+0050 u+0072 u+006F u+010D u+0070 u+0072 u+006F u+0073 u+0074
u+011B u+006E u+0065 u+006D u+006C u+0075 u+0076 u+00ED u+010D
u+0065 u+0073 u+006B u+0079
Punycode: Proprostnemluvesky-uyb24dma41a
]PRE]
Costello Standards Track [Page 14]
[PRE[
RFC 3492 IDNA Punycode March 2003
]PRE]
[PRE[
(E) Hebrew:
u+05DC u+05DE u+05D4 u+05D4 u+05DD u+05E4 u+05E9 u+05D5 u+05D8
u+05DC u+05D0 u+05DE u+05D3 u+05D1 u+05E8 u+05D9 u+05DD u+05E2
u+05D1 u+05E8 u+05D9 u+05EA
Punycode: 4dbcagdahymbxekheh6e0a7fei0b
]PRE]
[PRE[
(F) Hindi (Devanagari):
u+092F u+0939 u+0932 u+094B u+0917 u+0939 u+093F u+0928 u+094D
u+0926 u+0940 u+0915 u+094D u+092F u+094B u+0902 u+0928 u+0939
u+0940 u+0902 u+092C u+094B u+0932 u+0938 u+0915 u+0924 u+0947
u+0939 u+0948 u+0902
Punycode: i1baa7eci9glrd9b2ae1bj0hfcgg6iyaf8o0a1dig0cd
]PRE]
[PRE[
(G) Japanese (kanji and hiragana):
u+306A u+305C u+307F u+3093 u+306A u+65E5 u+672C u+8A9E u+3092
u+8A71 u+3057 u+3066 u+304F u+308C u+306A u+3044 u+306E u+304B
Punycode: n8jok5ay5dzabd5bym9f0cm5685rrjetr6pdxa
]PRE]
[PRE[
(H) Korean (Hangul syllables):
u+C138 u+ACC4 u+C758 u+BAA8 u+B4E0 u+C0AC u+B78C u+B4E4 u+C774
u+D55C u+AD6D u+C5B4 u+B97C u+C774 u+D574 u+D55C u+B2E4 u+BA74
u+C5BC u+B9C8 u+B098 u+C88B u+C744 u+AE4C
Punycode: 989aomsvi5e83db1d2a355cv1e0vak1dwrv93d5xbh15a0dt30a5j\
psd879ccm6fea98c
]PRE]
[PRE[
(I) Russian (Cyrillic):
U+043F u+043E u+0447 u+0435 u+043C u+0443 u+0436 u+0435 u+043E
u+043D u+0438 u+043D u+0435 u+0433 u+043E u+0432 u+043E u+0440
u+044F u+0442 u+043F u+043E u+0440 u+0443 u+0441 u+0441 u+043A
u+0438
Punycode: b1abfaaepdrnnbgefbaDotcwatmq2g4l
]PRE]
[PRE[
(J) Spanish: Porqu<eacute>nopuedensimplementehablarenEspa<ntilde>ol
U+0050 u+006F u+0072 u+0071 u+0075 u+00E9 u+006E u+006F u+0070
u+0075 u+0065 u+0064 u+0065 u+006E u+0073 u+0069 u+006D u+0070
u+006C u+0065 u+006D u+0065 u+006E u+0074 u+0065 u+0068 u+0061
u+0062 u+006C u+0061 u+0072 u+0065 u+006E U+0045 u+0073 u+0070
u+0061 u+00F1 u+006F u+006C
Punycode: PorqunopuedensimplementehablarenEspaol-fmd56a
]PRE]
[PRE[
(K) Vietnamese:
T<adotbelow>isaoh<odotbelow>kh<ocirc>ngth<ecirchookabove>ch\
<ihookabove>n<oacute>iti<ecircacute>ngVi<ecircdotbelow>t
U+0054 u+1EA1 u+0069 u+0073 u+0061 u+006F u+0068 u+1ECD u+006B
u+0068 u+00F4 u+006E u+0067 u+0074 u+0068 u+1EC3 u+0063 u+0068
u+1EC9 u+006E u+00F3 u+0069 u+0074 u+0069 u+1EBF u+006E u+0067
U+0056 u+0069 u+1EC7 u+0074
Punycode: TisaohkhngthchnitingVit-kjcr8268qyxafd2f1b9g
]PRE]
Costello Standards Track [Page 15]
[PRE[
RFC 3492 IDNA Punycode March 2003
]PRE]
[PRE[