Category : C Source Code
Archive   : BOEHMGC.ZIP
Filename : BOECHA.PS

 
Output of file : BOECHA.PS contained in archive : BOEHMGC.ZIP
%!PS-Adobe-2.0
%%Creator: dvips 5.519 Copyright 1986, 1993 Radical Eye Software
%%Title: boehmrep.dvi
%%CreationDate: Mon Jun 13 13:16:40 1994
%%Pages: 12
%%PageOrder: Ascend
%%BoundingBox: 0 0 612 792
%%EndComments
%DVIPSCommandLine: /usr/local/bin/dvips boehmrep
%DVIPSSource: TeX output 1994.06.13:1315
%%BeginProcSet: tex.pro
/TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N
/X{S N}B /TR{translate}N /isls false N /vsize 11 72 mul N /hsize 8.5 72
mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1}
ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale
isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div
hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul
TR matrix currentmatrix dup dup 4 get round 4 exch put dup dup 5 get
round 5 exch put setmatrix}N /@landscape{/isls true N}B /@manualfeed{
statusdict /manualfeed true put}B /@copies{/#copies X}B /FMat[1 0 0 -1 0
0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{/nn 8 dict N nn
begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N string /base X
array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N end dup{/foo
setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{/sf 1 N /fntrx
FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0]N df-tail}B /E{
pop nn dup definefont setfont}B /ch-width{ch-data dup length 5 sub get}
B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{128 ch-data dup
length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B
/ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup type
/stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N /rc 0 N /gp
0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2
index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff
ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice
ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 add]{
ch-image}imagemask restore}B /D{/cc X dup type /stringtype ne{]}if nn
/base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1
sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{cc 1 add D
}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin 0 0
moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul add
.99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore showpage
userdict /eop-hook known{eop-hook}if}N /@start{userdict /start-hook
known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X
/IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for
65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0
0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V
{}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7
getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false}
ifelse}{false}ifelse end{{gsave TR -.1 -.1 TR 1 1 scale rulex ruley
false RMat{BDot}imagemask grestore}}{{gsave TR -.1 -.1 TR rulex ruley
scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave
transform round exch round exch itransform moveto rulex 0 rlineto 0
ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta
0 N /tail{dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail}
B /c{-4 M}B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{
3 M}B /k{4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p
-1 w}B /q{p 1 w}B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{
3 2 roll p a}B /bos{/SS save N}B /eos{SS restore}B end
%%EndProcSet
TeXDict begin 40258431 52099146 1000 300 300
(/usr/johnl/jclt/i42/boehmrep.dvi) @start /Fa 1 50 df<03F80001F80007FE00
0FFE001E3F801C0300380FC03001802003E06000804001F0C000404000F9800040C0007F
00002080003F00002080003E00002080001F00002080000F80002080001F80002080001F
C00060400033E00040400061F000402000C0F800803001807E03801807003F8F000FFE00
0FFC0003F00003F8002B157D9432>49 D E /Fb 1 111 df<30F8590C4E0C9C0C980C18
0C180C30183019303130316032601C100D7F8C15>110 D E /Fc
13 120 df 000E000E00FFE0FFE00B147D9312>73 D 803FC03DC03CE038E03870387038383838FE7EFE7E0F147F9312>75
D F8FEF8FEF80F147F9312>78 D<1F303FF070F0E070E070E070E00070007F003FC00FE000
F0003800386038E038E030F070FFE0CF800D147E9312>83 D<3F807FC070E0207000700F
F03FF07870E070E070E07070F03FFE1F3E0F0E7E8D12>97 D<07801FE0387070706038E0
38FFF8FFF8E0006000703838381FF007C00D0E7E8D12>101 D<007E00FF01C703820380
03807FFEFFFE03800380038003800380038003800380038003803FF83FF81014809312>
I<06000F000F000600000000000000FF00FF000700070007000700070007000700070007
000700FFF0FFF00C157D9412>105 D 38383838FE3EFE3E0F0E7F8D12>110 D 0C381C3C383FF03BC038003800380038003800FE00FE000F157F8D12>112
D
114 D<06000E000E000E007FF8FFF80E000E000E000E000E000E000E000E380E380E3807
F003C00D127F9112>116 D 1CF01CF00F0E7F8D12>119 D E /Fd 11 123 df<60F0F06004047C830C>58
D<60F0F0701010101020204080040C7C830C>I<01F007080C0818043808300870307FC0
E000E000E000E000E000E0046008601030600F800E127E9113>101
D<0001E0000630000E78000CF0001C60001C00001C00001C00003C0000380000380003FF
C000380000380000700000700000700000700000700000E00000E00000E00000E00000E0
0001C00001C00001C00001C00001C000018000038000038000630000F30000F60000E400
0078000015257E9C14>I<381F81F04E20C6184640E81C4680F01C8F00F01C8E00E01C0E
00E01C0E00E01C1C01C0381C01C0381C01C0381C01C0703803807138038071380380E138
0380E2700700643003003820127E9124>109 D<381F004E61804681C04701C08F01C08E
01C00E01C00E01C01C03801C03801C03801C0700380710380710380E10380E2070064030
038014127E9119>I<07078009C86008D03008E03011C03011C03801C03801C038038070
0380700380700380600700E00700C00701800783000E86000E78000E00000E00001C0000
1C00001C00001C00003C0000FF8000151A819115>112 D<00C001C001C001C003800380
03800380FFF00700070007000E000E000E000E001C001C001C001C003820382038403840
18800F000C1A80990F>116 D<07878008C84010F0C020F1E020E3C040E18000E00000E0
0001C00001C00001C00001C000638080F38080F38100E5810084C60078780013127E9118
>120 D<1C00C02701C04701C04701C08703808703800E03800E03801C07001C07001C07
001C0700180E00180E00180E001C1E000C3C0007DC00001C00001800603800F03000F060
00E0C0004180003E0000121A7E9114>I<038107C10FE6081C1008001000200040008001
0002000400080410042C1877F843F081C010127E9113>I E /Fe
6 55 df<0C003C00CC000C000C000C000C000C000C000C000C000C000C000C000C00FF80
09107E8F0F>49 D<1F00618040C08060C0600060006000C00180030006000C0010202020
7FC0FFC00B107F8F0F>I<1F00218060C060C000C0008001800F00008000400060C060C0
60804060801F000B107F8F0F>I<0300030007000F000B001300330023004300C300FFE0
03000300030003001FE00B107F8F0F>I<20803F002C002000200020002F003080204000
6000600060C06080C061801F000B107F8F0F>I<0780184030C060C06000C000CF00F080
E040C060C060C060406060C030801F000B107F8F0F>I E /Ff 6
55 df<0C001C00EC000C000C000C000C000C000C000C000C000C000C000C000C000C000C
000C00FFC00A137D9211>49 D<1F0060C06060F070F030603000700070006000C001C001
80020004000810101020207FE0FFE00C137E9211>I<0FC0307070387038703800380030
00E00FC0007000380018001C601CF01CF018E03860701FC00E137F9211>I<006000E000
E00160026006600C600860106020606060C060FFFC0060006000600060006003FC0E137F
9211>I<60607FC07F8044004000400040004F0070C040E0006000700070E070E070E060
40E021C01F000C137E9211>I<07C00C201070207060006000C000CF00D0C0E060C020C0
30C030C03040306020206010C00F000C137E9211>I E /Fg 52 122
df<0001FC000703000C03001C07001C0300180000380000380000380000380000700007
FFFC00701C00701C00701C00E03800E03800E03800E03800E07001C07001C07001C07001
C0E201C0E201C0E20380E4038064038038038000030000070000060000C60000E40000CC
00007000001825819C17>12 D<183C3C3C0404080810204080060C779C0D>39
D<183878380808101020404080050C7D830D>44 DI<3078
F06005047C830D>I<00020006000C001C007C039C003800380038003800700070007000
7000E000E000E000E001C001C001C001C003800380038003800780FFF00F1C7C9B15>49
D<003C0000C3000101800201800201C00441C00441C00841C00841C00841C01083801083
801107000E0600000C0000180000300000C0000100000600000800001001001002002002
004006007E0C00C7F80083F80080E000121D7C9B15>I<003E0000C1800101800200C004
00C00440C00841C00841C00841C0088380070380000700000E0001F800003800000C0000
0C00000E00000E00000E00000E00700E00E01C00801C0080380080300040600021C0001F
0000121D7C9B15>I<00C06000FFC001FF8001FE00010000010000020000020000020000
020000047800058C00060600040600080600000700000700000600000E00000E00700E00
700C00E01C0080180080380040300040600021C0001F0000131D7C9B15>53
D<001E000061000081800180800300C00300C006018006018006018007030007860003CC
0003F00001F000037800063C00081E00180E00300E00600600600600600600C00C00C00C
00C0180060100060200030C0000F0000121D7C9B15>56 D<003C0000C600018300030300
0603000E03000C03801C03801C03001C0300380700380700380700380F00380E00181E00
181E000C6C00079C00001C00001800003800003000006000E0C000E0C000818000860000
7C0000111D7B9B15>I<0000180000001800000038000000380000007800000078000000
B8000001B800000138000002380000023C0000041C0000041C0000081C0000181C000010
1C0000201C0000201C00007FFC0000401C0000801C0001801C0001001C0002001C000200
1C0004000E000C000E001C001E00FF00FFC01A1D7E9C1F>65 D<01FFFE00003C07800038
03C0003801C0003801C0003801C0007001C0007003C0007003C00070078000E0070000E0
0E0000E03C0000FFF80001C01C0001C00E0001C00F0001C00F0003800F0003800F000380
0F0003800F0007001E0007001C0007003C00070078000E01E000FFFF80001A1C7D9B1D>
I<0003F020001E0C60003002E000E003C001C001C0038001C0070000C00E0000801E0000
801C0000803C0000803C000000780000007800000078000000F0000000F0000000F00000
00F0000000F0000400F0000400F0000400F0000800700008007000100038002000180040
000C0180000706000001F800001B1E7A9C1E>I<01FFFE00003C0780003801C0003801C0
003800E0003800E0007000F00070007000700070007000F000E000F000E000F000E000F0
00E000F001C001E001C001E001C001E001C001C0038003C0038003800380078003800700
07000E0007001C0007003800070070000E01C000FFFF00001C1C7D9B1F>I<01FFFFE000
3C00E0003800600038004000380040003800400070004000700040007020400070200000
E0400000E0400000E0C00000FFC00001C0800001C0800001C0800001C080000381010003
8001000380020003800200070004000700040007000C00070018000E007800FFFFF0001B
1C7D9B1C>I<01FFFFC0003C01C0003800C0003800800038008000380080007000800070
0080007020800070200000E0400000E0400000E0C00000FFC00001C0800001C0800001C0
800001C08000038100000380000003800000038000000700000007000000070000000700
00000F000000FFF000001A1C7D9B1B>I<0003F020001E0C60003002E000E003C001C001
C0038001C0070000C00E0000801E0000801C0000803C0000803C00000078000000780000
0078000000F0000000F0000000F001FFC0F0001E00F0001C00F0001C00F0001C00F0001C
00700038007000380038003800180078000C0090000707100001F800001B1E7A9C20>I<
01FFC0003C0000380000380000380000380000700000700000700000700000E00000E000
00E00000E00001C00001C00001C00001C000038000038000038000038000070000070000
0700000700000F0000FFE000121C7E9B10>73 D<01FFE0003C0000380000380000380000
380000700000700000700000700000E00000E00000E00000E00001C00001C00001C00001
C0000380080380080380080380100700100700300700600700E00E03C0FFFFC0151C7D9B
1A>76 D<01FE0007F8003E000780002E000F00002E001700002E001700002E002700004E
002E00004E004E00004E004E00004E008E00008E011C00008E011C00008E021C00008E02
1C0001070438000107043800010708380001071038000207107000020720700002072070
000207407000040740E000040780E000040700E0000C0700E0001C0601E000FF861FFC00
251C7D9B25>I<01FC03FE001C0070003C0060002E0040002E0040002E00400047008000
47008000470080004380800083810000838100008181000081C1000101C2000101C20001
00E2000100E2000200E4000200740002007400020074000400380004003800040038000C
0018001C001000FF8010001F1C7D9B1F>I<01FFFC00003C070000380380003801C00038
01C0003801C0007003C0007003C0007003C00070038000E0078000E0070000E00E0000E0
380001FFE00001C0000001C0000001C00000038000000380000003800000038000000700
00000700000007000000070000000F000000FFE000001A1C7D9B1C>80
D<01FFF800003C0E00003807000038038000380380003803800070078000700780007007
8000700F0000E00E0000E01C0000E0700000FFC00001C0C00001C0600001C0700001C070
00038070000380700003807000038070000700F0000700F0400700F0400700F0800F0078
80FFE0790000001E001A1D7D9B1E>82 D<000F8400304C00403C00801801001803001803
001806001006001006000007000007000003E00003FC0001FF00007F800007C00001C000
01C00000C00000C02000C02000C0600180600180600300600200F00400CC180083E00016
1E7D9C17>I<1FFFFFC01C0701C0300E00C0200E0080600E0080400E0080401C0080801C
0080801C0080001C00000038000000380000003800000038000000700000007000000070
00000070000000E0000000E0000000E0000000E0000001C0000001C0000001C0000001C0
000003C000007FFE00001A1C799B1E>I<7FF0FF800F001C000E0018000E0010000E0010
000E0010001C0020001C0020001C0020001C002000380040003800400038004000380040
0070008000700080007000800070008000E0010000E0010000E0010000E0020000E00200
00E0040000E00400006008000030300000104000000F800000191D779B1F>I F03C007001C038007001803800F001003800F00200380170020038017004003802700400
38027008001C047008001C047010001C087010001C087020001C107020001C107040001C
207040001C207080001C407180001C407100001C807200001D807200001D007400001E00
7400001E007800001C007800001C00700000180070000018006000001000600000241D77
9B29>87 D<01FF81FE001E00F0001C0060001E0080000E0180000E0100000F0200000704
0000070800000790000003A0000003C0000001C0000001C0000001E0000002E0000004E0
000008F0000010700000207000006038000040380000803C0001001C0002001C0006001E
001E001E00FF80FFC01F1C7E9B1F>I<03CC063C0C3C181C3838303870387038E070E070
E070E070E0E2C0E2C0E261E462643C380F127B9115>97 D<3F00070007000E000E000E00
0E001C001C001C001C0039C03E60383038307038703870387038E070E070E070E060E0E0
C0C0C1C0618063003C000D1D7B9C13>I<01F007080C08181C3838300070007000E000E0
00E000E000E000E008E010602030C01F000E127B9113>I<001F80000380000380000700
000700000700000700000E00000E00000E00000E0003DC00063C000C3C00181C00383800
303800703800703800E07000E07000E07000E07000E0E200C0E200C0E20061E400626400
3C3800111D7B9C15>I<01E007100C1018083810701070607F80E000E000E000E000E000
E0086010602030C01F000D127B9113>I<0003C0000670000C70001C60001C00001C0000
380000380000380000380000380003FF8000700000700000700000700000700000E00000
E00000E00000E00000E00001C00001C00001C00001C00001C00003800003800003800003
0000030000070000C60000E60000CC00007800001425819C0D>I<00F3018F030F06070E
0E0C0E1C0E1C0E381C381C381C381C383830383038187818F00F700070007000E000E0C0
C0E1C0C3007E00101A7D9113>I<0FC00001C00001C00003800003800003800003800007
00000700000700000700000E78000E8C000F0E000E0E001C0E001C0E001C0E001C0E0038
1C00381C00381C00383800703880703880707080707100E03200601C00111D7D9C15>I<
01800380010000000000000000000000000000001C002600470047008E008E000E001C00
1C001C0038003800710071007100720072003C00091C7C9B0D>I<0FC00001C00001C000
0380000380000380000380000700000700000700000700000E0F000E11000E23800E4380
1C83001C80001D00001E00003F800039C00038E00038E00070E20070E20070E20070E400
E06400603800111D7D9C13>107 D<1F800380038007000700070007000E000E000E000E
001C001C001C001C0038003800380038007000700070007000E400E400E400E400680038
00091D7C9C0B>I<3C1E0780266318C04683A0E04703C0E08E0380E08E0380E00E0380E0
0E0380E01C0701C01C0701C01C0701C01C070380380E0388380E0388380E0708380E0710
701C0320300C01C01D127C9122>I<3C3C002646004687004707008E07008E07000E0700
0E07001C0E001C0E001C0E001C1C00381C40381C40383840383880701900300E0012127C
9117>I<01E007180C0C180C380C300E700E700EE01CE01CE01CE018E038E030E06060C0
31801E000F127B9115>I<07870004D98008E0C008E0C011C0E011C0E001C0E001C0E003
81C00381C00381C00381800703800703000707000706000E8C000E70000E00000E00001C
00001C00001C00001C00003C0000FF8000131A7F9115>I<3C3C26C2468747078E068E00
0E000E001C001C001C001C0038003800380038007000300010127C9112>114
D<01F006080C080C1C18181C001F001FC00FF007F0007800386030E030C030806060C01F
000E127D9111>I<00C001C001C001C00380038003800380FFE00700070007000E000E00
0E000E001C001C001C001C00384038403840388019000E000B1A7D990E>I<1E03002707
00470700470700870E00870E000E0E000E0E001C1C001C1C001C1C001C1C003838803838
801838801839001C5900078E0011127C9116>I<1E06270E470E4706870287020E020E02
1C041C041C041C0818083808181018200C4007800F127C9113>I<1E0183270387470387
4703838707018707010E07010E07011C0E021C0E021C0E021C0E04180C04181C04181C08
1C1C100C263007C3C018127C911C>I<070E0019910010E38020E38041C30041C00001C0
0001C000038000038000038000038000070200670200E70400CB04008B080070F0001112
7D9113>I<1E03270747074707870E870E0E0E0E0E1C1C1C1C1C1C1C1C38383838183818
381C7007F00070007000E0E0C0E1C0818047003C00101A7C9114>I
E /Fh 58 125 df<0007E1F0001C173800703C3800E07C7801C0783001C0380001C03800
01C038000380700003807000038070003FFFFF0003807000038070000700E0000700E000
0700E0000700E0000700E0000700E0000E01C0000E01C0000E01C0000E01C0000E01C000
0E01C0001C0380001C03C000FF8FF8001D1D7F9C18>11 D<000100000001800000018000
000300000003000000030000000300000003000000030000000600000006000000060000
00060000FFFFFFC0FFFFFFC0000C0000000C0000000C0000000C0000000C0000000C0000
001800000018000000180000001800000018000000180000001000001A1C7C9720>43
D<387878380808101020204080050C7D830C>I<7FF0FFE00C027F890E>I<7070F0600404
7C830C>I<0018007003F00C7000700070007000E000E000E000E000E000E001C001C001
C001C001C001C003800380038003800380038007000780FFF80D1C7C9B15>49
D<007E000183800201C00400E00400E00F00E00F00E01F00E01F00E00E00E00001E00001
C0000380000380000700000E00001C0000380000600000C0000180000300800600800801
001001003FFF007FFE00FFFE00131C7E9B15>I<007C000187000203800403800F03C00F
03C00F03C00E0380000380000700000600000C0000380003F000001C00000E00000E0000
0F00000F00000F00700F00F80F00F80F00F00E00E01E00801C004038003070000FC00012
1D7D9B15>I<0000C0000180000380000380000780000B8000138000270000670000C700
008700010700020700040E00080E00180E00100E00200E00400E00FFFFC0001C00001C00
001C00001C00001C00003800003C0003FF80121C7E9B15>I<0301C003FF8003FE0007FC
0004000004000004000004000004000008000008F8000B0C000C0E000807000807000007
00000780000780000780700F00F00F00F00F00F00E00801E00801C0040380040300030E0
000F8000121D7D9B15>I<003E0000E1000180800303800607800C07801C070018000038
000030000071F000761800780C00E80E00F00600F00600E00700E00700E00700E00E00C0
0E00C00E00C00E00C01C00E0180060380060300030C0000F8000111D7C9B15>I<100000
3FFFC03FFFC03FFF8060010040020040040080080000080000100000200000400000C000
0080000180000180000300000700000700000F00000E00000E00001E00001E00001E0000
3C00003C00003C0000180000121D7B9B15>I<007C000183000201800601800C00C00C00
C00C00C01C01801C01801E03000F86000FCC0007F00003F80003FC000C7E00183F00300F
00600700600300C00300C00300C00300C00200C006006004006018003830000FC000121D
7D9B15>I<000020000000300000007000000070000000F0000000F0000001F000000378
00000278000006780000047800000C780000087C0000183C0000103C0000203C0000203C
0000403C0000403E0000FFFE0000801E0001001E0001001E0002001E0002000F0004000F
0004000F001E001F00FF80FFF01C1D7F9C1F>65 D<0FFFFC0000F8070000F0038000F003
C000F001C000F001E000F001E001E001C001E003C001E003C001E0078001E00F0001E03C
0003FFF80003C01E0003C00F0003C0078003C0078003C007800780078007800780078007
800780078007800F0007801E000F003C000F007800FFFFE0001B1C7E9B1D>I<0007F010
001C0C300070026000C001E0038000E0070000E00E0000600E0000601C0000403C000040
38000040780000007800000078000000F0000000F0000000F0000000F0000000F0000000
F0000080F0000100700001007000010038000200380004001C0004000C00180006002000
0380C000007F00001C1E7C9C1E>I<0FFFFC0000F8078000F001C000F000E000F0007000
F0007000F0007801E0003801E0003801E0003801E0003801E0003C01E0003803C0003803
C0007803C0007803C0007803C0007003C000F0078000E0078000E0078001C00780038007
80078007800E000F001C000F007000FFFFC0001E1C7E9B20>I<0FFFFFE000F801E000F0
00E000F0004000F0004000F0004000F0004001E0004001E0404001E0400001E0400001E0
C00001E1C00003FF800003C1800003C0800003C0800003C0800003C08080078000800780
0080078001000780010007800300078006000F000E000F003E00FFFFFC001B1C7E9B1C>
I<0007F010001C0C300070026000C001E0038000E0070000E00E0000600E0000601C0000
403C00004038000040780000007800000078000000F0000000F0000000F0000000F000FF
F0F0000F80F0000780F0000F0070000F0070000F0038000F0038000F001C001F000C001E
000600660003818200007E00001C1E7C9C21>71 D<0FFF9FFE00F803E000F003C000F003
C000F003C000F003C000F003C001E0078001E0078001E0078001E0078001E0078001E007
8003FFFF0003C00F0003C00F0003C00F0003C00F0003C00F0007801E0007801E0007801E
0007801E0007801E0007801E000F003C000F803E00FFF3FFC01F1C7E9B1F>I<0FFF8000
F80000F00000F00000F00000F00000F00001E00001E00001E00001E00001E00001E00003
C00003C00003C00003C00003C00003C0000780000780000780000780000780000780000F
00000F8000FFF800111C7F9B0F>I<01FFF0000F80000F00000F00000F00000F00000F00
001E00001E00001E00001E00001E00001E00003C00003C00003C00003C00003C00003C00
007800007800707800F87800F87800F0F000E0E00081C0004380003E0000141D7E9B15>
I<0FFFC000F80000F00000F00000F00000F00000F00001E00001E00001E00001E00001E0
0001E00003C00003C00003C00003C00003C00003C0040780040780040780040780080780
080780180F00380F00F0FFFFF0161C7E9B1A>76 D<0FF80007FC00F8000FC000BC000F80
00BC00178000BC00178000BC00278000BC002780011E004F00011E004F00011E008F0001
1E008F00011E010F00010F010F00020F021E00020F021E00020F041E00020F041E000207
881E000207901E000407903C000407A03C000407A03C000407C03C000403C03C00040380
3C000C038078001E03007C00FF8307FF80261C7E9B26>I<0FF807FE00F800F000FC0060
00BC004000BE0040009E0040009E0040010F0080010F008001078080010780800103C080
0103C0800201E1000201E1000200F1000200F1000200F9000200790004007E0004003E00
04003E0004001E0004001E0004000E000C000C001E000400FF8004001F1C7E9B1F>I<0F
FFFC0000F80F0000F0038000F003C000F001C000F001C000F001C001E003C001E003C001
E003C001E0038001E0070001E00E0003C03C0003FFE00003C0000003C0000003C0000003
C000000780000007800000078000000780000007800000078000000F0000000F800000FF
F000001A1C7E9B1C>80 D<0FFFF80000F80E0000F0078000F003C000F001C000F001E000
F001E001E003C001E003C001E0038001E0070001E00E0001E03C0003FFE00003C0700003
C0380003C03C0003C01C0003C01E0007803C0007803C0007803C0007803C0007803C0007
803C080F003C100F801C10FFF01C20000007C01D1D7E9B1F>82 D<003F0400C0CC018038
0300380600180E00180E00180E00181E00101E00001F00000F80000FF80007FF0003FF80
01FFC0003FE00003E00001E00000E00000E04000E04000E04000E04000C06001C0E00180
F00300CC0E0083F800161E7E9C17>I<1FFFFFF03C07C0F0300780302007802060078020
4007802040078020400F0020800F0020000F0000000F0000000F0000000F0000001E0000
001E0000001E0000001E0000001E0000001E0000003C0000003C0000003C0000003C0000
003C0000003C000000780000007C00001FFFE0001C1C7C9B1E>I 0006000F0004000F0004000F0004000F0004001E0008001E0008001E0008001E0008001E
0008001E0008003C0010003C0010003C0010003C0010003C0010003C0010007800200078
002000780020003800400038004000380080001C0100000C020000070C000001F000001B
1D7A9B1F>I 04000780080007C0080003C0100003C0100003C0200003C0200003E0400001E0400001E0
800001E1800001E1000001F2000000F2000000F4000000F4000000F8000000F800000070
00000070000000600000006000001D1D7B9B1F>I 0018000F000F0010000F001F0010000F001F0020000F002F0020000F002F0060000F804F
00400007804F804000078087808000078087808000078107810000078107810000078207
82000007C20782000003C407C4000003C403C4000003C803C8000003C803C8000003D803
D0000003D003D0000003F003E0000001E003E0000001E001C0000001C001C0000001C001
800000018001800000018001800000291D7B9B2B>I<07FF87FE00FE01F0007C01C0003C
0180003E0100001E0200001E0400001F0800000F1800000F90000007A0000007C0000003
C0000003E0000003E0000003F0000004F0000008F0000010F8000030780000207C000040
3C0000803E0001001E0003001F0006000F001F001F80FFC0FFF01F1C7F9B1F>I<07F000
1C18001E0C001C0E00180E00000E00000E0001FE000F0E001C1C00301C00701C00E01C40
E01C40E03C40E05C80709D803F0E0012127D9115>97 D<3F00000F00000E00000E00000E
00000E00000E00000E00001C00001C00001C00001C78001D86001E03003C038038018038
01803801C03801C03801C0700380700380700380700300700700700E00F00C00CC300083
C000121D7C9C17>I<01F8071C0C1E181C38183000700070007000E000E000E000600060
047008301018200FC00F127D9112>I<0003F00000F00000E00000E00000E00000E00000
E00000E00001C00001C00001C000F1C0030DC00C03C01C03803803803003807003807003
80700380E00700E00700E00700600700600700700F00301E00186F00078FC0141D7D9C17
>I<01F8070C0C061C073803300370037FFF7000E000E000E00060006002300430081C30
07C010127E9112>I<000F800039C00061C000E3C001C18001C00001C00001C000038000
0380000380003FF8000380000380000700000700000700000700000700000700000E0000
0E00000E00000E00000E00000E00001C00001E0000FFC000121D7F9C0D>I<000038003C
CC00C69C018308038380070380070380070380070380070700030600038C0004F0000400
000C00000C00000FFE0007FF800FFFC01801C02000C06000E0C000C0C000C06001802003
00180E0007F000161C809215>I<07E00001E00001C00001C00001C00001C00001C00001
C000038000038000038000038F8003B0C003C0E00780E00780E00700E00700E00700E007
00E00E01C00E01C00E01C00E01C00E01C00E01C01C03801E03C0FF9FF0141D7F9C17>I<
00C001C001C0018000000000000000000000000000001F80078003800700070007000700
070007000E000E000E000E000E000E001C001E00FF800A1D7F9C0C>I<07E00001E00001
C00001C00001C00001C00001C00001C0000380000380000380000387F80381E003818007
020007040007080007100007700007F8000F38000E3C000E1C000E1E000E0E000E0F001C
07001C0F80FF9FE0151D7F9C16>107 D<07E001E001C001C001C001C001C001C0038003
8003800380038003800700070007000700070007000E000E000E000E000E000E001C001E
00FF800B1D7F9C0C>I<1F8FC0FC00079061060003E07607000780780700078078070007
007007000700700700070070070007007007000E00E00E000E00E00E000E00E00E000E00
E00E000E00E00E000E00E00E001C01C01C001E01E01E00FF8FF8FF8021127F9124>I<1F
8F8007B0C003C0E00780E00780E00700E00700E00700E00700E00E01C00E01C00E01C00E
01C00E01C00E01C01C03801E03C0FF9FF014127F9117>I<00FC000307000E01801C01C0
3800C03000C07000E07000E07000E0E001C0E001C0E001C0600180600380700700380E00
1C180007E00013127E9115>I<0FC78003D86001E03003C03803803803801803801C0380
1C03801C0700380700380700380700700700700700E00F01C00EC3000E3C000E00000E00
000E00001C00001C00001C00001C0000FF8000161A809117>I<1F9C07EE03CF078E078C
07000700070007000E000E000E000E000E000E001C001E00FFC010127F9110>114
D<03F20C0E18061004300438043E001FE00FF007F8003C401C400C400C6018E010D0608F
C00F127F9110>I<020002000200060006000C001C003C00FFE01C001C00380038003800
380038003800700070407040704070407080708031001E000B1A7C9910>I 801C0380380700380700380700380700380700380700700E00700E00700E00700E00701E
00701E00703C00305E001F9F8011127C9117>I 04001E08000E08000E10000E10000E200007200007400007C00007800007000003000002
000013127C9116>I 001C2708001C2308001C4310000E4390000E83A0000E83A0000F03C0000F01C0000E0180
0006018000040100001B127C911E>I<1FE3FC07C1E003818001C10001C20000E40000EC
00007800007000003800007800009C00011E00020E000407000C07003C0780FE1FF01612
7F9116>I<0FF0FE03C03801C03001C02001C06001C04001E08000E08000E10000E10000
E200007200007400007C00007800007000003000002000002000004000004000708000F1
0000F10000E60000780000171A809116>I123
DI E /Fi 1 14 df<000FC000007FF80001F03E00038007
00060001800C0000C01800006030000030300000306000001860000018C000000CC00000
0CC000000CC000000CC000000CC000000CC000000C600000186000001830000030300000
30180000600C0000C0060001800380070001F03E00007FF800000FC0001E1D7E9623>13
D E /Fj 17 118 df<003F0401C08C0300580600380C0018180018380018700018700010
E00000E00000E00000E00000E00000E00020E00020E00020600040700040300080180300
0E0C0003F00016177C9619>67 D<03FF003C003800380038003800380038007000700070
00700070007000E000E000E000E0E0E0E1C0C1C0C3003E0010177D9612>74
D<1FFC0003C0000380000380000380000380000380000380000700000700000700000700
000700000700000E00100E00100E00100E00300E00200E00601C00E01C03C0FFFFC01417
7F9616>76 D<3FFFFC703C1C60380C403804C03804803804803804003800007000007000
00700000700000700000700000E00000E00000E00000E00000E00000E00001C00001E000
3FFE0016177C9619>84 D<0FE01C301C18081C001C03F81E3838386038E039E079E072E1
BA3E3C100E7E8D12>97 D<03E00C3018183018701C7FF8E000E000E000E0006008701038
600F800E0E7E8D10>101 D<007801CC039C030C07000700070007000E007FC00E000E00
0E000E001C001C001C001C001C001C0038003800FF000E177F960B>I<03E3C0063CC00C
18001C1C001C1C001838001838000C700017C0003000003000003FF0003FF8003FFC0060
0E00C00600C00600C00C00C018007070001FC00012157F8D12>I<1F8000078000070000
0700000700000700000700000700000E00000E3E000EC3000F03800E03800E03801C0700
1C07001C07001C07001C07001C0700380E00380E00FF3FC012177F9614>I<0307070600
000000003E0E0E0E0E1C1C1C1C1C1C3838FE08177F960A>I<1F80078007000700070007
00070007000E000E000E000E000E000E001C001C001C001C001C001C0038003800FF0009
177F960A>108 D<3E3E000EC3000F03800E03800E03801C07001C07001C07001C07001C
07001C0700380E00380E00FF3FC0120E7F8D14>110 D<03F00C18180C300E700E600EE0
0EE00EE00EE00C601C703838600F800F0E7E8D12>I<3E780E9C0F1C0E080E001C001C00
1C001C001C001C0038003800FF000E0E7F8D0E>114 D<07D018303010301038003F801F
C00FE000F040704020C060E0C09F000C0E7F8D0E>I<0400040004000C001C003800FF80
3800380038003800700070007000708070807080710071001E0009147D930E>I 0E380E380E380E701C701C701C701C701C703C603870F81F3F100E7D8D14>I
E /Fk 56 124 df<00FC000782000E07001C07001C02001C00001C00001C00001C0000FF
FF001C07001C07001C07001C07001C07001C07001C07001C07001C07001C07001C07001C
0700FF1FE01317809614>12 D<00FF000707000E07001C07001C07001C07001C07001C07
001C0700FFFF001C07001C07001C07001C07001C07001C07001C07001C07001C07001C07
001C07001C0700FFBFE01317809614>I<60F0F070101020204040040A7D830A>44
D<60F0F06004047D830A>46 D<0008001800300030003000600060006000C000C000C001
8001800180030003000600060006000C000C000C00180018001800300030003000600060
006000C000C0000D217E9812>I<03000700FF0007000700070007000700070007000700
0700070007000700070007000700070007007FF00C157E9412>49
D<0F8030E040708030C038E0384038003800700070006000C00180030006000C08080810
183FF07FF0FFF00D157E9412>I<00300030007000F001F0017002700470087018701070
20704070C070FFFE0070007000700070007003FE0F157F9412>52
D<01F00608080C181C301C70006000E000E3E0EC30F018F00CE00EE00EE00E600E600E30
0C3018183007C00F157F9412>54 D<40007FFE7FFC7FF8C0088010802000400080008001
00010003000200060006000E000E000E000E000E0004000F167E9512>I<07C018303018
6018E00CE00CE00EE00EE00E601E301E186E0F8E000E000C001C70187018603020C01F80
0F157F9412>57 D<60F0F06000000000000060F0F060040E7D8D0A>I<00100000380000
3800003800005C00005C00005C00008E00008E00008E0001070001070003078002038002
038007FFC00401C00401C00800E00800E01800E03800F0FE03FE17177F961A>65
D C01C00E01C00701C00301C00381C00381C00381C00381C00701C00E01C01C0FFFF001517
7F9619>I<00FC100383300E00B01C0070380030300030700010600010E00010E00000E0
0000E00000E00000E00000E000106000107000103000203800201C00400E008003830000
FC0014177E9619>I 1C000E1C000E1C000E1C000E1C000E1C000E1C000C1C001C1C001C1C00381C00301C0060
1C01C0FFFF0017177F961B>I 001C04001C04001C0C001FFC001C0C001C04001C04081C04081C00081C00181C00101C00
101C00301C00F0FFFFF015177F9618>I 00101C04001C04001C04001C0C001FFC001C0C001C04001C04001C04001C00001C00001C
00001C00001C00001C0000FFC00014177F9617>I 000E000E000E000E000E000E000E000E000E000E000E000E000E000E00FFE00B177F960D
>73 D 101C10100E10100F101007101003901001D01001D01000F0100070100030380030FE0010
17177F961A>78 D<00FC000303000E01C01C00E0380070300030700038600018E0001CE0
001CE0001CE0001CE0001CE0001CE0001C7000387000383000303800701C00E00E01C003
030000FC0016177E961B>I 1C00601C00C01C03801FFE001C00001C00001C00001C00001C00001C00001C00001C0000
1C00001C0000FF800014177F9618>I 701C00701C00E01C00C01C03801FFE001C07801C01C01C00E01C00E01C00E01C00E01C00
E01C00E11C00E11C0072FF803C18177F961A>82 D<0FC4302C601C400CC004C004C004E0
0070007F003FE00FF801FC001C000E0006800680068006C004E008D81087E00F177E9614
>I<7FFFF860381840380840380880380480380480380400380000380000380000380000
380000380000380000380000380000380000380000380000380000380000380007FFC016
177F9619>I 1C00101C00101C00101C00101C00101C00101C00101C00100E0020060020030040018180
007E0017177F961A>I 4003808003808003C18001C10001C10000E20000E20000F6000074000074000038000038
0000380000100017177F961A>I 780000700000E00000E00001C0000380000380000700800F00800E00801C01803C010038
0100700300700F00FFFF0011177E9616>90 D C0C0C0C0C0C0C0C0C0C0C0C0C0C0FCFC06217D980A>I 0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0CFCFC062180980A>93
D<1FC0386038301038003803F81E3830387038E039E039E07970FF1F1E100E7F8D12>97
D 001C03801C01801C01C01C01C01C01C01C01C01C01801C03801C03001B0E0010F8001217
809614>I<07F01838303870106000E000E000E000E000600070083008183007C00D0E7F
8D10>I<007E00000E00000E00000E00000E00000E00000E00000E00000E0007CE001C3E
00300E00700E00600E00E00E00E00E00E00E00E00E00600E00700E00301E00182E0007CF
C012177F9614>I<0FC0186030307038E018FFF8E000E000E000600070083010183007C0
0D0E7F8D10>I<03E006700E701C201C001C001C001C001C00FF801C001C001C001C001C
001C001C001C001C001C001C001C00FF800C1780960B>I<0F9E18E33060707070707070
306018C02F80200060003FE03FF83FFC600EC006C006C006600C38380FE010157F8D12>
I 001C07001C07001C07001C07001C07001C07001C07001C07001C07001C0700FF9FE01317
809614>I<183C3C1800000000007C1C1C1C1C1C1C1C1C1C1C1C1CFF081780960A>I<0300
078007800300000000000000000000001F80038003800380038003800380038003800380
0380038003800380038003804380E300E7007C00091D82960B>I 1C00001C00001C00001C00001C00001C00001C3F801C1C001C18001C20001C40001CC000
1FE0001CF0001C70001C78001C3C001C1E001C1E00FF3FC01217809613>I 001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C
001C00FF80091780960A>I 1C0701C01C0701C01C0701C01C0701C01C0701C01C0701C01C0701C0FF9FE7F81D0E808D
1E>I 1C07001C0700FF9FE0130E808D14>I<07C018303018600C600CE00EE00EE00EE00EE00E
701C3018183007C00F0E7F8D12>I 1C01C01C01C01C01801C03801C07001F0E001CF8001C00001C00001C00001C00001C0000
FF80001214808D14>I FF800D0E808D0E>114 D<1F4060C0C040C040E000FF007F801FC001E080608060C060E0
C09F000B0E7F8D0E>I<080008000800180018003800FF80380038003800380038003800
380038403840384038401C800F000A147F930E>I 1C07001C07001C07001C07001C07001C07001C0F000E170003E7E0130E808D14>I 3C0E3C0C1C081C080E100E100720072003C003C003C001800180100E7F8D13>I 3838383838101C3C201C3C201C4C200E4E400E4E400E8640078780078780070380030300
030300160E7F8D19>I FC7F100E7F8D13>I 8001000100E200E200A400780010147F8D13>I 1E081C08381870107030FFF00D0E7F8D10>II
E /Fl 1 4 df<0C000C008C40EDC07F800C007F80EDC08C400C000C000A0B7D8B10>3
D E /Fm 70 123 df<60F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0600000000060F0F0600419
779816>33 D<0387000387000387000387000387000387007FFFC0FFFFE0FFFFE0070E00
070E00070E000E1C000E1C000E1C000E1C00FFFFE0FFFFE07FFFC01C38001C38001C3800
1C38001C38001C380013197F9816>35 D<00C00001C00001C00001C00007F0001FFC003F
FE007DCF0071C780E1C380E1C780E1C780F1C30079C0003FC0001FF00007FC0001FE0001
CF0001C70061C380F1C380F1C380E1C38071C70079DF003FFE001FF80007E00001C00001
C00000C00011207E9C16>I<30787C3C1C1C1C1C3878F0E040060D789816>39
D<00E001E0038007000E001C001C0038003800700070007000E000E000E000E000E000E0
00E000E000E000700070007000380038001C001C000E000700038001E000E00B217A9C16
>I 01C001C001C001C0038003800380070007000E000E001C0038007000E000C0000A217B9C
16>I<01C00001C00001C00001C00071C700F9CF807FFF001FFC0007F00007F0001FFC00
7FFF00F9CF8071C70001C00001C00001C00001C00011127E9516>I<01C00001C00001C0
0001C00001C00001C00001C00001C000FFFF80FFFF80FFFF8001C00001C00001C00001C0
0001C00001C00001C00001C00011137E9516>I<387C7E7E3E0E1E1C78F060070B798416>
II<70F8F8F8700505788416>I<0001800003800003
80000700000700000E00000E00001C00001C0000380000380000700000700000E00000E0
0001C00001C0000380000380000700000700000E00000E00001C00001C00003800003800
00700000700000E00000E00000C0000011207E9C16>I<03E0000FF8001FFC001E3C0038
0E00780F00700700700700E00380E00380E00380E00380E00380E00380E00380E00380F0
0780700700700700780F003C1E001E3C001FFC000FF80003E00011197E9816>I<018003
80038007800F807F80FF8073800380038003800380038003800380038003800380038003
80038003807FF87FFC7FF80E197C9816>I<07E0001FF8003FFC00783E00E00700F00780
F00380600380000380000380000700000700000E00001C0000380000700000E00001C000
0380000F00001E03803803807FFF80FFFF807FFF8011197E9816>I<07E0001FF8003FFC
00781E00780700300700000700000700000E00003E0007FC0007F00007FC00001E000007
00000300000380000380600380F00380E00700781E003FFC001FF80007E00011197E9816
>I<007C0000FC0000DC0001DC00039C00039C00071C000F1C000E1C001E1C003C1C0038
1C00781C00F01C00FFFFE0FFFFE0FFFFE0001C00001C00001C00001C00001C0001FFC001
FFC001FFC013197F9816>I<3FFE003FFE003FFE00380000380000380000380000380000
3800003800003BF0003FFC003FFE003C0F00300700000380000380600380F00380F00380
E00700781E003FFC001FF80007E00011197E9816>I<00F80003FC0007FE000F07001C0F
00380F00780600700000700000E3F800EFFC00FFFE00F80F00F00700F00380E00380E003
807003807003807007803807003C1E001FFC000FF80003E00011197E9816>I<387C7C7C
38000000000000000038787C7C3C1C1C3870E0400618799116>59
D<000180000780001F80003E0000F80001F00007C0000F80003E0000FC0000F00000FC00
003E00000F800007C00001F00000F800003E00001F8000078000018011157E9616>I<7F
FF00FFFF80FFFF80000000000000000000000000000000FFFF80FFFF807FFF00110B7E91
16>I 001F80003E0000F80001F00007C0000F80003E0000FC0000F00000C0000011157E9616>
I<00E00001F00001F00001B00001B00003B80003B80003B800031800071C00071C00071C
00071C00071C000E0E000E0E000FFE000FFE001FFF001C07001C07001C07007F1FC0FF1F
E07F1FC013197F9816>65 D<7FF800FFFE007FFF001C0F001C07801C03801C03801C0380
1C07801C07001FFF001FFE001FFE001C1F001C03801C03C01C01C01C01C01C01C01C01C0
1C03C01C07807FFF80FFFF007FFC0012197F9816>I<01F18007FB800FFF801F0F803C07
80380380700380700380F00000E00000E00000E00000E00000E00000E00000E00000F000
007003807003803803803C07001F0F000FFE0007FC0001F00011197E9816>I<7FF800FF
FE007FFF001C0F001C07801C03C01C01C01C01C01C01E01C00E01C00E01C00E01C00E01C
00E01C00E01C00E01C00E01C01C01C01C01C03C01C07801C0F807FFF00FFFE007FF80013
19809816>I<7FFFC0FFFFC07FFFC01C01C01C01C01C01C01C01C01C00001C00001C1C00
1C1C001FFC001FFC001FFC001C1C001C1C001C00001C00E01C00E01C00E01C00E01C00E0
7FFFE0FFFFE07FFFE013197F9816>I E01C00001C00001C1C001C1C001FFC001FFC001FFC001C1C001C1C001C00001C00001C00
001C00001C00001C0000FF8000FFC000FF800013197F9816>I<03E30007FF000FFF001E
1F003C0F00380700700700700700F00000E00000E00000E00000E00000E03F80E07FC0E0
3F80F00700700700700700380F003C0F001E1F000FFF0007F70003E70012197E9816>I<
7F1FC0FFBFE07F1FC01C07001C07001C07001C07001C07001C07001C07001FFF001FFF00
1FFF001C07001C07001C07001C07001C07001C07001C07001C07001C07007F1FC0FFBFE0
7F1FC013197F9816>I 038003800380038003800380038003800380FFFEFFFEFFFE0F197D9816>I<7F0FE0FF8F
F07F0FE01C07801C0F001C0E001C1C001C3C001C78001CF0001CE0001DF0001FF0001FF8
001F38001E1C001C1C001C0E001C0E001C07001C07001C03807F07E0FF8FF07F07E01419
809816>75 D 1C00001C00001C00001C00001C00001C00001C00001C00401C00E01C00E01C00E01C00E0
FFFFE0FFFFE0FFFFE013197F9816>I<7E1FC0FF3FE07F1FC01D07001D87001D87001D87
001DC7001DC7001CC7001CC7001CE7001CE7001CE7001C67001C67001C77001C77001C37
001C37001C37001C17007F1F00FF9F007F0F0013197F9816>78 D<1FFC003FFE007FFF00
780F00F00780E00380E00380E00380E00380E00380E00380E00380E00380E00380E00380
E00380E00380E00380E00380F00780F00780780F007FFF003FFE001FFC0011197E9816>
I<7FF800FFFE007FFF001C0F801C03801C03C01C01C01C01C01C01C01C03C01C03801C0F
801FFF001FFE001FF8001C00001C00001C00001C00001C00001C00001C00007F0000FF80
007F000012197F9816>I<7FE000FFF8007FFC001C1E001C0F001C07001C07001C07001C
07001C0F001C1E001FFC001FF8001FFC001C1C001C0E001C0E001C0E001C0E001C0E201C
0E701C0E707F07E0FF87E07F03C014197F9816>82 D<07E3001FFF003FFF00781F00F007
00E00700E00700E00000F000007800003F80001FF00007FC0000FE00000F000007000003
80000380600380E00380E00700F80F00FFFE00FFFC00C7F00011197E9816>I<7F07F0FF
8FF87F07F01C01C01C01C01C01C01C01C01C01C01C01C01C01C01C01C01C01C01C01C01C
01C01C01C01C01C01C01C01C01C01C01C00E03800E038007070007FF0003FE0000F80015
19809816>85 D 000E0E000E0E00060C00071C00071C00071C00071C0003180003B80003B80003B80001B0
0001F00001F00000E00013197F9816>I 018038038038038038038038E38039F38039F38039B38019B30019B30019B30019B30019
B30019B3001913001B1B000F1E000F1E000E0E0013197F9816>I<7FFF80FFFF80FFFF80
E00700E00F00E01E00E01C00003C0000780000700000F00001E00001C00003C000078000
0700000F00001E03801C03803C0380780380700380FFFF80FFFF80FFFF8011197E9816>
90 D 00E000E000E000E000E000E000E000E000E000E000E000E000FFF0FFF0FFF00C20789C16
>I 007000700070007000700070007000700070007000700070FFF0FFF0FFF00C207F9C16>
93 D95 D<1FE0003FF0007FF800783C00300E0000
0E00000E0003FE001FFE003E0E00700E00E00E00E00E00E00E00783E007FFFE03FE7E00F
83E013127E9116>97 D<7E0000FE00007E00000E00000E00000E00000E00000E3E000EFF
000FFF800F83C00F00E00E00E00E00700E00700E00700E00700E00700E00700E00E00F01
E00F83C00FFF800EFF00063C001419809816>I<03F80FFC1FFE3C1E780C7000E000E000
E000E000E000F000700778073E0E1FFC0FF803F010127D9116>I<003F00007F00003F00
00070000070000070000070003C7000FF7001FFF003C1F00780F00700700E00700E00700
E00700E00700E00700E00700700F00700F003C1F001FFFE00FE7F007C7E014197F9816>
I<03E00FF81FFC3C1E780E7007E007FFFFFFFFFFFFE000E000700778073C0F1FFE0FFC03
F010127D9116>I<001F00007F8000FF8001E78001C30001C00001C0007FFF00FFFF00FF
FF0001C00001C00001C00001C00001C00001C00001C00001C00001C00001C00001C00001
C0003FFE007FFF003FFE0011197F9816>I<03E3C007F7E00FFFE01C1CC0380E00380E00
380E00380E00380E001C1C000FF8001FF0001BE0003800001800001FFC001FFF003FFF80
7803C0E000E0E000E0E000E0E000E07001C07C07C03FFF800FFE0003F800131C7F9116>
I<7E0000FE00007E00000E00000E00000E00000E00000E3C000EFE000FFF000F87800F03
800E03800E03800E03800E03800E03800E03800E03800E03800E03800E03807FC7F0FFE7
F87FC7F01519809816>I<018003C003C0018000000000000000007FC07FC07FC001C001
C001C001C001C001C001C001C001C001C001C001C07FFFFFFF7FFF101A7D9916>I<7E00
00FE00007E00000E00000E00000E00000E00000E7FE00E7FE00E7FE00E0F000E1E000E3C
000E78000EF0000FF0000FF8000FBC000F1E000E0E000E07000E07807F87F0FFCFF07F87
F01419809816>107 D 0001C00001C00001C00001C00001C00001C00001C00001C00001C00001C00001C00001C0
0001C000FFFF80FFFF80FFFF8011197E9816>I 70E03870E03870E03870E03870E03870E03870E03870E03870E03870E0FE7CF8FE7CF8FE
3C781512809116>I<7E3C00FEFE007FFF000F87800F03800E03800E03800E03800E0380
0E03800E03800E03800E03800E03800E03807FC7F0FFE7F87FC7F01512809116>I<03E0
000FF8001FFC003C1E00780F00700700E00380E00380E00380E00380E00380F007807007
00780F003C1E001FFC000FF80003E00011127E9116>I<7E3E00FEFF007FFF800F83C00F
00E00E00E00E00700E00700E00700E00700E00700E00700E00E00F01E00F83C00FFF800E
FF000E3C000E00000E00000E00000E00000E00000E00007FC000FFE0007FC000141B8091
16>I 070000070000070000070000FFFC00FFFC00FFFC0013127F9116>114
D<0FEC3FFC7FFCF03CE01CE01C70007F801FF007F8003C600EE00EF00EF81EFFFCFFF8C7
E00F127D9116>I<0300000700000700000700000700007FFF00FFFF00FFFF0007000007
000007000007000007000007000007000007010007038007038007038007870003FE0001
FC0000F80011177F9616>I<7E1F80FE3F807E1F800E03800E03800E03800E03800E0380
0E03800E03800E03800E03800E03800E03800E0F800FFFF007FBF803E3F01512809116>
I<7F1FC0FF1FE07F1FC01C07001E0F000E0E000E0E000E0E00071C00071C00071C00071C
0003B80003B80003B80001F00001F00000E00013127F9116>I 038038038038038038038038E38019F30019F30019B3001DB7001DB7001DB7001DB7000F
1E000F1E000F1E0013127F9116>I<7F1FC07F3FC07F1FC00F1C00073C0003B80003F000
01F00000E00001E00001F00003B800073C00071C000E0E007F1FC0FF3FE07F1FC013127F
9116>I<7F1FC0FF9FE07F1FC01C07000E07000E0E000E0E00070E00071C00071C00039C
00039C0003980001B80001B80000F00000F00000F00000E00000E00000E00001C00079C0
007BC0007F80003F00003C0000131B7F9116>I<3FFFC07FFFC07FFFC0700780700F0070
1E00003C0000780001F00003E0000780000F00001E01C03C01C07801C0FFFFC0FFFFC0FF
FFC012127F9116>I E /Fn 32 122 df 067F9017>45 D<000003800000000007C00000000007C0000000000FE0000000000FE000
0000000FE0000000001FF0000000001FF0000000003FF8000000003FF8000000003FF800
00000073FC0000000073FC00000000F3FE00000000E1FE00000000E1FE00000001C0FF00
000001C0FF00000003C0FF80000003807F80000007807FC0000007003FC0000007003FC0
00000E003FE000000E001FE000001E001FF000001C000FF000001FFFFFF000003FFFFFF8
00003FFFFFF80000780007FC0000700003FC0000700003FC0000E00001FE0000E00001FE
0001E00001FF0001C00000FF0001C00000FF00FFFE001FFFFEFFFE001FFFFEFFFE001FFF
FE2F297EA834>65 D 0FF80003F80007FC0003F80003FC0003F80003FC0003F80003FE0003F80001FE0003F800
01FE0003F80001FE0003F80003FE0003F80003FC0003F80003FC0003F80007F80003F800
0FF00003F8001FE00003F800FFC00003FFFFFE000003FFFFFFE00003F80007F00003F800
03FC0003F80001FE0003F80001FE0003F80000FF0003F80000FF0003F80000FF8003F800
00FF8003F80000FF8003F80000FF8003F80000FF8003F80000FF8003F80000FF0003F800
01FF0003F80003FE0003F80007FC0003F8001FF800FFFFFFFFF000FFFFFFFFC000FFFFFF
FE000029297DA831>I<00003FF001800003FFFE0380000FFFFF8780003FF007DF8000FF
8001FF8001FE00007F8003FC00003F8007F000001F800FF000000F801FE0000007801FE0
000007803FC0000007803FC0000003807FC0000003807F80000003807F8000000000FF80
00000000FF8000000000FF8000000000FF8000000000FF8000000000FF8000000000FF80
00000000FF8000000000FF80000000007F80000000007F80000000007FC0000003803FC0
000003803FC0000003801FE0000003801FE0000007000FF00000070007F000000E0003FC
00001E0001FE00003C0000FF8000F800003FF007E000000FFFFFC0000003FFFF00000000
3FF8000029297CA832>I FC0007FC0003FC0001FE0003FC0000FF0003FC00007F8003FC00003FC003FC00001FC003
FC00001FE003FC00001FE003FC00000FF003FC00000FF003FC00000FF003FC00000FF003
FC00000FF803FC00000FF803FC00000FF803FC00000FF803FC00000FF803FC00000FF803
FC00000FF803FC00000FF803FC00000FF803FC00000FF803FC00000FF003FC00000FF003
FC00000FF003FC00001FE003FC00001FE003FC00001FC003FC00003FC003FC00007F8003
FC00007F0003FC0001FE0003FC0003FC0003FC001FF800FFFFFFFFE000FFFFFFFF8000FF
FFFFFC00002D297DA835>I<00007FE003000003FFFC0700001FFFFF0F00003FF00FFF00
00FF8001FF0001FE0000FF0003F800003F0007F000003F000FF000001F001FE000000F00
1FE000000F003FC000000F003FC0000007007FC0000007007F80000007007F8000000000
FF8000000000FF8000000000FF8000000000FF8000000000FF8000000000FF8000000000
FF8000000000FF8000000000FF8001FFFFF87F8001FFFFF87F8001FFFFF87FC00000FF00
3FC00000FF003FC00000FF001FE00000FF001FE00000FF000FF00000FF0007F00000FF00
03F80000FF0001FE0000FF0000FF8001FF00003FF007BF00001FFFFF1F000003FFFE0F00
00007FF003002D297CA836>71 D FE0001FE0001FE0001FE0001FE0001FE0001FE0001FE0001FE0001FE0001FE0001FE0001
FE0001FE0001FE0001FE0001FE0001FE0001FE0001FE0001FE0001FE0001FE0001FE0001
FE0001FE0001FE0001FE0001FE0001FE0001FE00FFFFFCFFFFFCFFFFFC16297EA81A>73
D 03FC00000003FC00000003FC00000003FC00000003FC00000003FC00000003FC00000003
FC00000003FC00000003FC00000003FC00000003FC00000003FC00000003FC00000003FC
00000003FC00000003FC00000003FC0001C003FC0001C003FC0001C003FC0001C003FC00
03C003FC00038003FC00038003FC00078003FC00078003FC000F8003FC000F8003FC001F
8003FC007F8003FC01FF00FFFFFFFF00FFFFFFFF00FFFFFFFF0022297DA829>76
D 03FC0003FC03FC0003FE03FC0003FE03FC0003FE03FC0003FE03FC0003FE03FC0003FE03
FC0003FE03FC0003FC03FC0007FC03FC0007F803FC000FF003FC003FE003FFFFFF8003FF
FFFE0003FC00000003FC00000003FC00000003FC00000003FC00000003FC00000003FC00
000003FC00000003FC00000003FC00000003FC00000003FC00000003FC00000003FC0000
0003FC00000003FC000000FFFFF00000FFFFF00000FFFFF0000027297DA82F>80
D 0003FC0007FC0003FC0003FC0003FC0003FE0003FC0003FE0003FC0003FE0003FC0003FE
0003FC0003FE0003FC0003FE0003FC0003FC0003FC0007F80003FC0007F80003FC001FE0
0003FC007FC00003FFFFFE000003FFFFF0000003FC00FC000003FC007F000003FC003F80
0003FC003F800003FC001FC00003FC001FE00003FC001FE00003FC001FE00003FC001FE0
0003FC001FE00003FC001FF00003FC001FF00003FC001FF00003FC001FF00703FC001FF8
0703FC000FF80703FC0007F80EFFFFF003FE1CFFFFF001FFF8FFFFF0003FF030297DA834
>82 D<007F806003FFF0E007FFF9E00F807FE01F001FE03E0007E07C0003E07C0001E0FC
0001E0FC0001E0FC0000E0FE0000E0FE0000E0FF000000FFC000007FFE00007FFFE0003F
FFFC001FFFFE000FFFFF8007FFFFC003FFFFE000FFFFE00007FFF000007FF000000FF800
0007F8000003F8600001F8E00001F8E00001F8E00001F8F00001F0F00001F0F80003F0FC
0003E0FF0007C0FFE01F80F3FFFF00E0FFFE00C01FF0001D297CA826>I<01FF800007FF
F0000F81F8001FC07E001FC07E001FC03F000F803F8007003F8000003F8000003F800000
3F80000FFF8000FFFF8007FC3F800FE03F803F803F803F003F807F003F80FE003F80FE00
3F80FE003F80FE003F807E007F807F00DF803F839FFC0FFF0FFC01FC03FC1E1B7E9A21>
97 D 00000FE00000000FE00000000FE00000000FE00000000FE00000000FE00000000FE00000
000FE00000000FE1FE00000FE7FF80000FFE07E0000FF801F0000FF000F8000FE000FC00
0FE000FE000FE0007F000FE0007F000FE0007F000FE0007F800FE0007F800FE0007F800F
E0007F800FE0007F800FE0007F800FE0007F800FE0007F000FE0007F000FE0007F000FE0
00FE000FE000FC000FF001F8000FF803F0000F9E07E0000F07FF80000E01FC0000212A7E
A926>I<001FF80000FFFE0003F01F0007E03F800FC03F801F803F803F801F007F800E00
7F0000007F000000FF000000FF000000FF000000FF000000FF000000FF000000FF000000
7F0000007F0000007F8000003F8001C01F8001C00FC0038007E0070003F01E0000FFFC00
001FE0001A1B7E9A1F>I<00003FF80000003FF80000003FF800000003F800000003F800
000003F800000003F800000003F800000003F800000003F800000003F800000003F80000
0003F800000003F800000003F800001FE3F80000FFFBF80003F03FF80007E00FF8000FC0
07F8001F8003F8003F8003F8007F0003F8007F0003F8007F0003F800FF0003F800FF0003
F800FF0003F800FF0003F800FF0003F800FF0003F800FF0003F8007F0003F8007F0003F8
007F0003F8003F8003F8001F8003F8000F8007F80007C00FF80003F03BFF8000FFF3FF80
003FC3FF80212A7EA926>I<003FE00001FFF80003F07E0007C01F000F801F801F800F80
3F800FC07F000FC07F0007C07F0007E0FF0007E0FF0007E0FFFFFFE0FFFFFFE0FF000000
FF000000FF0000007F0000007F0000007F0000003F8000E01F8000E00FC001C007E00380
03F81F0000FFFE00001FF0001B1B7E9A20>I<0007F0003FFC00FE3E01F87F03F87F03F0
7F07F07F07F03E07F00007F00007F00007F00007F00007F00007F000FFFFC0FFFFC0FFFF
C007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F0
0007F00007F00007F00007F00007F00007F00007F00007F00007F0007FFF807FFF807FFF
80182A7EA915>I<00FF81F003FFE7F80FC1FE7C1F80FC7C1F007C383F007E107F007F00
7F007F007F007F007F007F007F007F007F007F003F007E001F007C001F80FC000FC1F800
1FFFE00018FF800038000000380000003C0000003E0000003FFFF8001FFFFF001FFFFF80
0FFFFFC007FFFFE01FFFFFF03E0007F07C0001F8F80000F8F80000F8F80000F8F80000F8
7C0001F03C0001E01F0007C00FC01F8003FFFE00007FF0001E287E9A22>I<07000FC01F
E03FE03FE03FE01FE00FC007000000000000000000000000000000FFE0FFE0FFE00FE00F
E00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00F
E00FE0FFFEFFFEFFFE0F2B7DAA14>105 D 00000FE000000FE000000FE000000FE000000FE000000FE000000FE000000FE000000FE0
00000FE000000FE01FFC0FE01FFC0FE01FFC0FE007800FE00F000FE01E000FE03C000FE0
78000FE0E0000FE3C0000FE7C0000FEFE0000FFFE0000FFFF0000FF3F8000FE3F8000FC1
FC000FC0FE000FC07F000FC07F000FC03F800FC01FC00FC00FC00FC00FE0FFFC3FFEFFFC
3FFEFFFC3FFE1F2A7EA924>107 D E00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00F
E00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE0FFFEFFFEFFFE0F2A7DA914>I 7F800FF000FFC1FFE03FFC00FFC383F0707E000FC603F8C07F000FCC01F9803F000FD801
FF003F800FF001FE003F800FF001FE003F800FE001FC003F800FE001FC003F800FE001FC
003F800FE001FC003F800FE001FC003F800FE001FC003F800FE001FC003F800FE001FC00
3F800FE001FC003F800FE001FC003F800FE001FC003F800FE001FC003F800FE001FC003F
800FE001FC003F800FE001FC003F800FE001FC003F80FFFE1FFFC3FFF8FFFE1FFFC3FFF8
FFFE1FFFC3FFF8351B7D9A3A>I 03F0000FD803F8000FF003F8000FF003F8000FE003F8000FE003F8000FE003F8000FE003
F8000FE003F8000FE003F8000FE003F8000FE003F8000FE003F8000FE003F8000FE003F8
000FE003F8000FE003F8000FE003F8000FE003F8000FE003F800FFFE3FFF80FFFE3FFF80
FFFE3FFF80211B7D9A26>I<003FE00001FFFC0003F07E000FC01F801F800FC03F800FE0
3F0007E07F0007F07F0007F07F0007F0FF0007F8FF0007F8FF0007F8FF0007F8FF0007F8
FF0007F8FF0007F8FF0007F87F0007F07F0007F03F800FE03F800FE01F800FC00FC01F80
07F07F0001FFFC00003FE0001D1B7E9A22>I 03F0000FF001F8000FE000FC000FE000FE000FE000FF000FE0007F000FE0007F000FE000
7F800FE0007F800FE0007F800FE0007F800FE0007F800FE0007F800FE0007F800FE0007F
000FE000FF000FE000FF000FE000FE000FE001FC000FF001F8000FF803F0000FFE0FE000
0FE7FF80000FE1FC00000FE00000000FE00000000FE00000000FE00000000FE00000000F
E00000000FE00000000FE00000000FE0000000FFFE000000FFFE000000FFFE0000002127
7E9A26>I E0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000F
E0000FE000FFFF00FFFF00FFFF00181B7E9A1C>114 D<03FE300FFFF01E03F03800F070
0070F00070F00070F80070FC0000FFE0007FFE007FFF803FFFE01FFFF007FFF800FFF800
03FC0000FC60007CE0003CF0003CF00038F80038FC0070FF01E0F7FFC0C1FF00161B7E9A
1B>I<00700000700000700000700000F00000F00000F00001F00003F00003F00007F000
1FFFF0FFFFF0FFFFF007F00007F00007F00007F00007F00007F00007F00007F00007F000
07F00007F00007F00007F00007F03807F03807F03807F03807F03807F03803F03803F870
01F86000FFC0001F8015267FA51B>I 0FE003F8000FE003F8000FE003F8000FE003F8000FE003F8000FE003F8000FE003F8000F
E003F8000FE003F8000FE003F8000FE003F8000FE003F8000FE003F8000FE003F8000FE0
03F8000FE003F8000FE003F8000FE007F80007E007F80007E00FF80003F03BFF8001FFF3
FF80003FC3FF80211B7D9A26>I 00700007F800F00003F800E00003FC01E00001FC01C00001FC01C00000FE03800000FE03
8000007F070000007F070000007F8F0000003F8E0000003FDE0000001FDC0000001FDC00
00000FF80000000FF80000000FF800000007F000000007F000000003E000000003E00000
0001C00000211B7F9A24>I 07F003F001C007F003F001C007F807F803C003F807F8038003F807F8038001FC0EFC0700
01FC0EFC070001FE1EFC0F0000FE1C7E0E0000FE1C7E0E0000FF383F1E00007F383F1C00
007F783F3C00003FF01FB800003FF01FB800003FF01FF800001FE00FF000001FE00FF000
000FC007E000000FC007E000000FC007E00000078003C00000078003C0002F1B7F9A32>
I 03FC01E00001FC01C00001FC01C00000FE03800000FE038000007F070000007F07000000
7F8F0000003F8E0000003FDE0000001FDC0000001FDC0000000FF80000000FF80000000F
F800000007F000000007F000000003E000000003E000000001C000000001C00000000380
0000000380000038078000007C07000000FE0F000000FE0E000000FE1E000000FE3C0000
007C780000003FE00000000FC000000021277F9A24>121 D E /Fo
81 124 df<007E1F0001C1B1800303E3C00703C3C00E03C1800E01C0000E01C0000E01C0
000E01C0000E01C0000E01C000FFFFFC000E01C0000E01C0000E01C0000E01C0000E01C0
000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0
000E01C0000E01C0007F87FC001A1D809C18>11 D<007E0001C1800301800703C00E03C0
0E01800E00000E00000E00000E00000E0000FFFFC00E01C00E01C00E01C00E01C00E01C0
0E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C07F87F8
151D809C17>I<007FC001C1C00303C00703C00E01C00E01C00E01C00E01C00E01C00E01
C00E01C0FFFFC00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01
C00E01C00E01C00E01C00E01C00E01C00E01C07FCFF8151D809C17>I<003F07E00001C0
9C18000380F018000701F03C000E01E03C000E00E018000E00E000000E00E000000E00E0
00000E00E000000E00E00000FFFFFFFC000E00E01C000E00E01C000E00E01C000E00E01C
000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C00
0E00E01C000E00E01C000E00E01C000E00E01C000E00E01C007FC7FCFF80211D809C23>
I<6060F0F0F8F86868080808080808101010102020404080800D0C7F9C15>34
D<60F0F8680808081010204080050C7C9C0C>39 D<004000800100020006000C000C0018
001800300030007000600060006000E000E000E000E000E000E000E000E000E000E000E0
00E000600060006000700030003000180018000C000C00060002000100008000400A2A7D
9E10>I<800040002000100018000C000C000600060003000300038001800180018001C0
01C001C001C001C001C001C001C001C001C001C001C00180018001800380030003000600
06000C000C00180010002000400080000A2A7E9E10>I<60F0F070101010102020408004
0C7C830C>44 DI<60F0F06004047C830C>I<0001000300060006
0006000C000C000C0018001800180030003000300060006000C000C000C0018001800180
030003000300060006000C000C000C00180018001800300030003000600060006000C000
C00010297E9E15>I<03C00C301818300C300C700E60066006E007E007E007E007E007E0
07E007E007E007E007E007E007E00760066006700E300C300C18180C3007E0101D7E9B15
>I<030007003F00C7000700070007000700070007000700070007000700070007000700
0700070007000700070007000700070007000F80FFF80D1C7C9B15>I<07C01830201C40
0C400EF00FF80FF807F8077007000F000E000E001C001C00380070006000C00180030006
010C01180110023FFE7FFEFFFE101C7E9B15>I<07E01830201C201C781E780E781E381E
001C001C00180030006007E00030001C001C000E000F000F700FF80FF80FF80FF00E401C
201C183007E0101D7E9B15>I<000C00000C00001C00003C00003C00005C0000DC00009C
00011C00031C00021C00041C000C1C00081C00101C00301C00201C00401C00C01C00FFFF
C0001C00001C00001C00001C00001C00001C00001C0001FFC0121C7F9B15>I<300C3FF8
3FF03FC020002000200020002000200023E024302818301C200E000E000F000F000F600F
F00FF00FF00F800E401E401C2038187007C0101D7E9B15>I<00F0030C06040C0E181E30
1E300C700070006000E3E0E430E818F00CF00EE006E007E007E007E007E0076007600770
06300E300C18180C3003E0101D7E9B15>I<4000007FFF807FFF007FFF00400200800400
80040080080000100000100000200000600000400000C00000C00001C000018000018000
038000038000038000038000078000078000078000078000078000078000030000111D7E
9B15>I<03E00C301008200C20066006600660067006780C3E083FB01FE007F007F818FC
307E601E600FC007C003C003C003C00360026004300C1C1007E0101D7E9B15>I<03C00C
301818300C700C600EE006E006E007E007E007E007E0076007700F300F18170C2707C700
060006000E300C780C78187010203030C00F80101D7E9B15>I<60F0F060000000000000
0000000060F0F06004127C910C>I<60F0F0600000000000000000000060F0F070101010
1020204080041A7C910C>I<7FFFFFC0FFFFFFE000000000000000000000000000000000
00000000000000000000000000000000FFFFFFE07FFFFFC01B0C7E8F20>61
D<0FE03038401CE00EF00EF00EF00E000C001C0030006000C00080018001000100010001
00010001000000000000000000000003000780078003000F1D7E9C14>63
D<003F800000C0600003001800040004000800020010000100201F00802070808040E040
4040C0384041C03840818038208380382083803820838038208380382083803820818038
2041C0382040C0384040E0784020709880201F0F00100000000800000004000000030001
E000C01F80003FF0001B1D7E9C20>I<000600000006000000060000000F0000000F0000
000F00000017800000178000001780000023C0000023C0000023C0000041E0000041E000
0041E0000080F0000080F0000180F8000100780001FFF80003007C0002003C0002003C00
06003E0004001E0004001E000C001F001E001F00FF80FFF01C1D7F9C1F>I F00F00380F003C0F001C0F001E0F001E0F001E0F001E0F001C0F003C0F00780F01F00FFF
E00F00780F003C0F001E0F000E0F000F0F000F0F000F0F000F0F000F0F001E0F001E0F00
3C0F0078FFFFE0181C7E9B1D>I<001F808000E0618001801980070007800E0003801C00
03801C00018038000180780000807800008070000080F0000000F0000000F0000000F000
0000F0000000F0000000F0000000F0000000700000807800008078000080380000801C00
01001C0001000E000200070004000180080000E03000001FC000191E7E9C1E>I 000F00F0000F003C000F000E000F0007000F0007000F0003800F0003C00F0001C00F0001
C00F0001E00F0001E00F0001E00F0001E00F0001E00F0001E00F0001E00F0001E00F0001
C00F0001C00F0003C00F0003800F0007800F0007000F000E000F001C000F007000FFFFC0
001B1C7E9B20>I 02000F02000F02000F06000FFE000F06000F02000F02000F02000F02010F00010F00020F
00020F00020F00060F00060F000C0F003CFFFFFC181C7E9B1C>I 0F00080F00080F000C0F00040F00040F02040F02000F02000F02000F06000FFE000F0600
0F02000F02000F02000F02000F00000F00000F00000F00000F00000F00000F00000F8000
FFF800161C7E9B1B>I<001F808000E0618001801980070007800E0003801C0003801C00
018038000180780000807800008070000080F0000000F0000000F0000000F0000000F000
0000F0000000F000FFF0F0000F80700007807800078078000780380007801C0007801C00
07800E00078007000B800180118000E06080001F80001C1E7E9C21>I 000F003C000F003C000F003C000F003C000F003C000F003C000F003C000F003C000F003C
000F003C000F003C000FFFFC000F003C000F003C000F003C000F003C000F003C000F003C
000F003C000F003C000F003C000F003C000F003C000F003C000F003C00FFF3FFC01A1C7E
9B1F>I 0F000F000F000F000F000F000F000F000F000F000F00FFF00C1C7F9B0F>I<1FFF00F800
780078007800780078007800780078007800780078007800780078007800780078007800
787078F878F878F878F0F040E021C01F00101D7F9B15>I 0F0008000F0010000F0020000F0040000F0080000F0100000F0200000F0400000F0E0000
0F1F00000F2F00000F2780000F4780000F83C0000F01E0000F01E0000F00F0000F00F800
0F0078000F003C000F003C000F001E000F001F000F001F80FFF07FF01C1C7E9B20>I F8000F80000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F
00000F00000F00000F00000F00000F00000F00080F00080F00080F00180F00180F00100F
00300F00700F01F0FFFFF0151C7E9B1A>I 78000BC00178000BC001780009E002780009E002780008F004780008F004780008F00478
00087808780008780878000878087800083C107800083C107800083C107800081E207800
081E207800081E207800080F407800080F40780008078078000807807800080780780008
030078001C03007800FF8307FF80211C7E9B26>I 0009E0040009E0040008F0040008F8040008780400083C0400083C0400081E0400080F04
00080F0400080784000807C4000803C4000801E4000801E4000800F40008007C0008007C
0008003C0008003C0008001C0008000C001C000C00FF8004001A1C7E9B1F>I<003F8000
00E0E0000380380007001C000E000E001C0007003C00078038000380780003C0780003C0
700001C0F00001E0F00001E0F00001E0F00001E0F00001E0F00001E0F00001E0F00001E0
700001C0780003C0780003C0380003803C0007801C0007000E000E0007001C0003803800
00E0E000003F80001B1E7E9C20>I 0F001E0F001E0F001E0F001C0F003C0F00780F00E00FFF800F00000F00000F00000F0000
0F00000F00000F00000F00000F00000F00000F00000F0000FFF000171C7E9B1C>I 00000F01E0000F0078000F003C000F001C000F001E000F001E000F001E000F001E000F00
1C000F003C000F0078000F01E0000FFF00000F03C0000F00E0000F00F0000F0078000F00
78000F0078000F0078000F0078000F0078000F0078100F0078100F0038100F003C20FFF0
1C20000007C01C1D7E9B1F>82 D<07E0801C1980300580700380600180E00180E00080E0
0080E00080F00000F800007C00007FC0003FF8001FFE0007FF0000FF80000F800007C000
03C00001C08001C08001C08001C0C00180C00180E00300D00200CC0C0083F800121E7E9C
17>I<7FFFFFC0700F01C0600F00C0400F0040400F0040C00F0020800F0020800F002080
0F0020000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F000000
0F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F000000
1F800003FFFC001B1C7F9B1E>I 04000F0004000F0004000F0004000F0004000F0004000F0004000F0004000F0004000F00
04000F0004000F0004000F0004000F0004000F0004000F0004000F000400070008000780
0800038010000180100000C020000070C000001F00001A1D7E9B1F>I C00F0001800F0001000F800300078002000780020003C0040003C0040003C0040001E008
0001E0080001F0080000F0100000F0100000F830000078200000782000003C4000003C40
00003C4000001E8000001E8000001F8000000F0000000F00000006000000060000000600
001C1D7F9B1F>I 001007801F00200780278020078027802003C027804003C043C04003C043C04003E043C0
4001E081E08001E081E08001E081E08000F100F10000F100F10000F100F100007900FA00
007A007A00007A007A00003E007C00003C003C00003C003C00003C003C00001800180000
180018000018001800281D7F9B2B>I<7FF0FFC00FC03E000780180003C0180003E01000
01E0200001F0600000F0400000788000007D8000003D0000001E0000001F0000000F0000
000F8000000F80000013C0000023E0000021E0000041F00000C0F8000080780001007C00
03003C0002001E0006001F001F003F80FFC0FFF01C1C7F9B1F>I<7FFFF07C01F07001E0
6003C06003C0400780400F80400F00401E00001E00003C00007C0000780000F00000F000
01E00003E00003C0100780100780100F00101F00301E00203C00203C00607800E0F803E0
FFFFE0141C7E9B19>90 D C0C0C0C0C0C0C0C0C0C0C0C0C0C0FEFE07297C9E0C>I<08081010202040404040808080
808080B0B0F8F8787830300D0C7A9C15>I 060606060606060606060606060606060606060606FEFE0729809E0C>I<1FC000307000
783800781C00301C00001C00001C0001FC000F1C00381C00701C00601C00E01C40E01C40
E01C40603C40304E801F870012127E9115>97 D 00001C00001C00001C00001C00001C00001C7C001D86001E03001C01801C01C01C00C01C
00E01C00E01C00E01C00E01C00E01C00E01C00C01C01C01C01801E030019060010F80013
1D7F9C17>I<07E00C301878307870306000E000E000E000E000E000E000600070043004
18080C3007C00E127E9112>I<003F000007000007000007000007000007000007000007
0000070000070000070003E7000C1700180F00300700700700600700E00700E00700E007
00E00700E00700E00700600700700700300700180F000C370007C7E0131D7E9C17>I<03
E00C301818300C700E6006E006FFFEE000E000E000E00060007002300218040C1803E00F
127F9112>I<00F8018C071E061E0E0C0E000E000E000E000E000E00FFE00E000E000E00
0E000E000E000E000E000E000E000E000E000E000E000E000E007FE00F1D809C0D>I<00
038003C4C00C38C01C3880181800381C00381C00381C00381C001818001C38000C300013
C0001000003000001800001FF8001FFF001FFF803003806001C0C000C0C000C0C000C060
01803003001C0E0007F800121C7F9215>I 1C00001C00001C00001C00001C00001C7C001C87001D03001E03801C03801C03801C0380
1C03801C03801C03801C03801C03801C03801C03801C03801C03801C0380FF9FF0141D7F
9C17>I<18003C003C0018000000000000000000000000000000FC001C001C001C001C00
1C001C001C001C001C001C001C001C001C001C001C001C00FF80091D7F9C0C>I<00C001
E001E000C000000000000000000000000000000FE000E000E000E000E000E000E000E000
E000E000E000E000E000E000E000E000E000E000E000E000E060E0F0C0F1C061803E000B
25839C0D>I 1C00001C3FC01C0F001C0C001C08001C10001C20001C40001CE0001DE0001E70001C7800
1C38001C3C001C1C001C0E001C0F001C0F80FF9FE0131D7F9C16>I 1C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C00
1C001C001C001C001C001C00FF80091D7F9C0C>I 1E01E01C001C01C01C001C01C01C001C01C01C001C01C01C001C01C01C001C01C01C001C
01C01C001C01C01C001C01C01C001C01C01C001C01C01C001C01C01C001C01C01C00FF8F
F8FF8021127F9124>I 801C03801C03801C03801C03801C03801C03801C03801C0380FF9FF014127F9117>I<03
F0000E1C00180600300300700380600180E001C0E001C0E001C0E001C0E001C0E001C060
01807003803003001806000E1C0003F00012127F9115>I 1C01C01C00C01C00E01C00E01C00E01C00E01C00E01C00E01C01C01C01C01C01801E0300
1D06001CF8001C00001C00001C00001C00001C00001C00001C0000FF8000131A7F9117>
I<03C1000C3300180B00300F00700700700700E00700E00700E00700E00700E00700E007
00600700700700300F00180F000C370007C7000007000007000007000007000007000007
00000700003FE0131A7E9116>I 1C001C001C001C001C001C00FFC00D127F9110>I<1F9030704030C010C010E010F8007F
803FE00FF000F880388018C018C018E010D0608FC00D127F9110>I<0400040004000400
0C000C001C003C00FFE01C001C001C001C001C001C001C001C001C001C101C101C101C10
1C100C100E2003C00C1A7F9910>I 1C03801C03801C03801C03801C03801C03801C03801C07800C07800E1B8003E3F014127F
9117>I 0003D80001D00001D00000E00000E00000E00000400013127F9116>I 801C0701801C0701001C0B01000E0B82000E0B82000E1182000711C4000711C4000720C4
0003A0E80003A0E80003C0680001C0700001C0700001803000008020001B127F911E>I<
7F8FF00F03800F030007020003840001C80001D80000F00000700000780000F800009C00
010E00020E000607000403801E07C0FF0FF81512809116>I 000E02000E020007040007040007040003880003880003D80001D00001D00000E00000E0
0000E000004000004000008000008000F08000F10000F300006600003C0000131A7F9116
>I<7FFC70386038407040F040E041C003C0038007000F040E041C043C0C380870087038
FFF80E127F9112>II E /Fp 27 119 df<78FCFCFEFE7A02020404
08083040070E7D9C0D>39 D<0020004001800380030006000E001C001C003C0038003800
780078007800F800F000F000F000F000F000F000F000F000F000F8007800780078003800
38003C001C001C000E000600030003800180004000200B297C9E13>I<80004000300038
0018000C000E000700070007800380038003C003C003C003E001E001E001E001E001E001
E001E001E001E003E003C003C003C0038003800780070007000E000C0018003800300040
0080000B297D9E13>I45 D<78FCFCFCFC7806067D85
0D>I<00038000000380000007C0000007C0000007C000000FE000000FE000001FF00000
1BF000001BF0000031F8000031F8000061FC000060FC0000E0FE0000C07E0000C07E0001
803F0001FFFF0003FFFF8003001F8003001F8006000FC006000FC00E000FE00C0007E0FF
C07FFEFFC07FFE1F1C7E9B24>65 D C007E00FC007E00FC007E00FC007E00FC007E00FC007C00FC00F800FC03F000FFFFE000F
C00F800FC007C00FC007E00FC003E00FC003F00FC003F00FC003F00FC003F00FC003F00F
C007E00FC007E00FC01FC0FFFFFF00FFFFFC001C1C7E9B22>I<001FE02000FFF8E003F8
0FE007C003E00F8001E01F0000E03E0000E03E0000607E0000607C000060FC000000FC00
0000FC000000FC000000FC000000FC000000FC000000FC0000007C0000607E0000603E00
00603E0000C01F0000C00F80018007C0030003F80E0000FFFC00001FE0001B1C7D9B22>
I 7C0FC0007C0FC0007E0FC0007E0FC0007E0FC0007E0FC0007E0FC0007E0FC0007E0FC000
7E0FC0007C0FC0007C0FC0007C0FC000F80FC000F80FC001F00FC007E00FC01FC0FFFFFF
00FFFFF8001F1C7E9B25>I 0FC003F00FC003F00FC003F00FC003F00FC003F00FC003F00FFFFFF00FFFFFF00FC003F0
0FC003F00FC003F00FC003F00FC003F00FC003F00FC003F00FC003F00FC003F00FC003F0
0FC003F00FC003F0FFFC3FFFFFFC3FFF201C7E9B25>72 D 07E007E007E007E007E007E007E007E007E007E007E007E007E007E007E007E007E007E0
07E007E0FFFFFFFF101C7F9B12>I<07FFF007FFF0001F80001F80001F80001F80001F80
001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80
001F80301F80781F80FC1F80FC1F80FC1F00783E00387C000FF000141C7F9B19>I 01FF80FFFC01FF800FC000180007E000300007E000300007F000700003F000600003F800
E00001F800C00001FC00C00000FC01800000FC018000007E030000007E030000007F0700
00003F060000003F8E0000001F8C0000001FCC0000000FD80000000FD800000007F00000
0007F000000007F000000003E000000003E000000001C000000001C00000211C7F9B24>
86 D<0FF8001C1E003E0F803E07803E07C01C07C00007C0007FC007E7C01F07C03C07C0
7C07C0F807C0F807C0F807C0780BC03E13F80FE1F815127F9117>97
D 801FE1E01F80701F00781F003C1F003C1F003E1F003E1F003E1F003E1F003E1F003E1F00
3C1F003C1F00781F80701EC1E01C3F00171D7F9C1B>I<03FC000E0E001C1F003C1F0078
1F00780E00F80000F80000F80000F80000F80000F800007800007801803C01801C03000E
0E0003F80011127E9115>I<000FF0000FF00001F00001F00001F00001F00001F00001F0
0001F00001F00001F001F9F00F07F01C03F03C01F07801F07801F0F801F0F801F0F801F0
F801F0F801F0F801F07801F07801F03C01F01C03F00F0FFE03F9FE171D7E9C1B>I<01FC
000F07001C03803C01C07801C07801E0F801E0F801E0FFFFE0F80000F80000F800007800
007C00603C00601E00C00F038001FC0013127F9116>I 00001F00001F00001F00001F00001F00001F00001F0FC01F31E01F40F01F80F81F80F81F
00F81F00F81F00F81F00F81F00F81F00F81F00F81F00F81F00F81F00F81F00F8FFE7FFFF
E7FF181D7F9C1B>104 D<1E003F003F003F003F001E00000000000000000000000000FF
00FF001F001F001F001F001F001F001F001F001F001F001F001F001F001F00FFE0FFE00B
1E7F9D0E>I 1F00F807C01F00F807C01F00F807C01F00F807C01F00F807C01F00F807C01F00F807C01F
00F807C01F00F807C01F00F807C0FFE7FF3FF8FFE7FF3FF825127F9128>109
D F81F00F81F00F81F00F81F00F8FFE7FFFFE7FF18127F911B>I<01FC000F07801C01C03C
01E07800F07800F0F800F8F800F8F800F8F800F8F800F8F800F87800F07800F03C01E01E
03C00F078001FC0015127F9118>I 1F00001F00001F00001F00001F00001F00001F00001F00001F0000FFF000FFF00011127F
9114>114 D<1FD830786018E018E018F000FF807FE07FF01FF807FC007CC01CC01CE01C
E018F830CFC00E127E9113>I<0300030003000300070007000F000F003FFCFFFC1F001F
001F001F001F001F001F001F001F001F0C1F0C1F0C1F0C0F08079803F00E1A7F9913>I<
FFC1FCFFC1FC1F00601F80E00F80C00FC0C007C18007C18003E30003E30001F60001F600
01FE0000FC0000FC0000780000780000300016127F9119>118 D
E /Fq 5 104 df<01800180018001804182F18F399C0FF003C003C00FF0399CF18F4182
018001800180018010127E9215>3 D<000001800000078000001E00000078000001E000
00078000001E00000078000001E00000078000001E00000078000000E000000078000000
1E0000000780000001E0000000780000001E0000000780000001E0000000780000001E00
000007800000018000000000000000000000000000000000000000000000000000000000
7FFFFF00FFFFFF8019227D9920>20 D<0000030000000003000000000180000000018000
000000C00000000060007FFFFFF000FFFFFFF8000000000E00000000070000000001E000
0000007800000001E0000000038000000006000000001C00FFFFFFF8007FFFFFF0000000
006000000000C000000001800000000180000000030000000003000025187E952A>41
D<003C00E001C00180038003800380038003800380038003800380038003800380038003
0007001C00F0001C00070003000380038003800380038003800380038003800380038003
800380018001C000E0003C0E297D9E15>102 D 038003800380038003800380038003800380018001C000E0003C00E001C0018003800380
03800380038003800380038003800380038003800380030007001C00F0000E297D9E15>
I E /Fr 24 117 df45 D<78FCFCFCFC7806067B8511>I<
00100000700001F0000FF000FEF000F0F00000F00000F00000F00000F00000F00000F000
00F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F000
00F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F000
00F00001F8007FFFE07FFFE013287BA71E>49 D<007F000003FFC0000701F0000C00F800
10007C001C007C003E007E003E003E003E003E001E003E000C007E0000007C0000007C00
000078000000F0000000E0000001C0000007000000FF00000001E0000000F00000007800
00003C0000003E0000001F0000001F0000001F8000001F8030001F8078001F80FC001F80
FC001F80FC001F00F8001F0040003F0040003E0030007C001800F8000F01F00003FFC000
007F000019297EA71E>51 D<00001800000000180000000018000000003C000000003C00
0000003C000000007E000000007E00000000FF000000009F000000009F000000011F8000
00010F800000010F8000000207C000000207C000000207C000000403E000000403E00000
0403E000000801F000000801F000001801F800001000F800001000F800002000FC000020
007C00003FFFFC00007FFFFE000040003E000040003E000080001F000080001F00008000
1F000100000F800100000F800100000F8002000007C007000007C01F80000FE0FFF000FF
FFFFF000FFFF282A7EA92D>65 D<0000FF00100007FFE030001FC07830003E000C7000F8
0006F001F00003F003E00001F007C00000F00F800000700F800000701F000000303F0000
00303E000000303E000000107E000000107E000000107C00000000FC00000000FC000000
00FC00000000FC00000000FC00000000FC00000000FC00000000FC00000000FC00000000
7C000000007E000000007E000000103E000000103E000000103F000000101F000000200F
800000200F8000006007C000004003E000008001F000018000F8000300003E000E00001F
C038000007FFE0000000FF8000242B7DA92B>67 D<0000FF00100007FFE030001FC07830
003E000C7000F80006F001F00003F003E00001F007C00000F00F800000700F800000701F
000000303F000000303E000000303E000000107E000000107E000000107C00000000FC00
000000FC00000000FC00000000FC00000000FC00000000FC00000000FC00000000FC0000
0000FC0000FFFF7C0000FFFF7E000003F07E000001F03E000001F03E000001F03F000001
F01F000001F00F800001F00F800001F007C00001F003E00001F001F00002F000F80002F0
003E000C70001FC038300007FFE0100000FF8000282B7DA92F>71
D 03E00007C003E00007E003E00007E003E00007E003E00007E003E00007E003E00007E003
E00007C003E0000FC003E0000F8003E0001F0003E0003E0003E001F80003FFFFE00003E0
00000003E000000003E000000003E000000003E000000003E000000003E000000003E000
000003E000000003E000000003E000000003E000000003E000000003E000000003E00000
0003E000000003E000000007F0000000FFFF800000FFFF80000023297EA829>80
D<00FE010003FF83000F81E3001E0037003C001F0038000F007800070070000700F00003
00F0000300F0000300F0000100F8000100F8000100FC0000007C0000007F0000003FE000
001FFF00000FFFE00007FFF80003FFFC00007FFE000007FF0000007F0000001F8000000F
80000007C0000007C0800003C0800003C0800003C0800003C0C00003C0C0000380C00003
80E0000780F0000700F8000E00EE001C00C3C07800C1FFF000803FC0001A2B7DA921>83
D<01FC00000E0780001001C0003C00E0003E00F0003E0078001C00780008007800000078
000000780000007800007FF80003E078000F8078001F0078003E0078007C007800780078
20F8007820F8007820F8007820F800F8207C00F8203C013C401F063FC007F80F001B1A7E
991E>97 D<07800000FF800000FF8000000F800000078000000780000007800000078000
0007800000078000000780000007800000078000000780000007800000078000000783F0
00078C1C0007B0070007A0038007C003C0078001E0078001E0078000F0078000F0078000
F8078000F8078000F8078000F8078000F8078000F8078000F8078000F0078000F0078001
F0078001E0078001C007C003C00740078007200E0006181C000407E0001D2A7FA921>I<
007F8001C0700780080F003C1E007C3C007C3C00387C0010780000F80000F80000F80000
F80000F80000F80000F80000F800007800007C00003C00043C00041E00080F0010078020
01C0C0007F00161A7E991B>I<007E0003C3800700E00E00F01C00703C00783C00387800
3C78003CF8003CF8003CFFFFFCF80000F80000F80000F80000F800007800007C00003C00
043C00041E00080E001007002001C0C0007F00161A7E991B>101
D<001F000070C000E1E001C3E003C3E00381C00780800780000780000780000780000780
00078000078000078000078000FFFE00FFFE000780000780000780000780000780000780
000780000780000780000780000780000780000780000780000780000780000780000780
0007800007800007800007C000FFFE00FFFE00132A7FA912>I<0000078001FC18400707
21C00E03C1C01E03C0803C01E0003C01E0007C01F0007C01F0007C01F0007C01F0007C01
F0003C01E0003C01E0001E03C0000E0380001707000011FC000030000000300000003000
0000380000001C0000001FFFC0000FFFF80007FFFC001C003E0030000F00700007006000
0380E0000380E0000380E0000380E0000380700007007000070038000E000C0018000780
F00000FF80001A287E9A1E>I<07000F801F801F800F8007000000000000000000000000
0000000000000007807F807F800F80078007800780078007800780078007800780078007
80078007800780078007800780078007800780FFF8FFF80D297FA811>105
D<0780FF80FF800F80078007800780078007800780078007800780078007800780078007
800780078007800780078007800780078007800780078007800780078007800780078007
800780078007800780FFFCFFFC0E2A7FA911>108 D<0781F800FC00FF860E030700FF98
070C03800FA0079003C007A003D001E007C003E001E007C003E001E0078003C001E00780
03C001E0078003C001E0078003C001E0078003C001E0078003C001E0078003C001E00780
03C001E0078003C001E0078003C001E0078003C001E0078003C001E0078003C001E00780
03C001E0078003C001E0078003C001E0078003C001E0FFFC7FFE3FFFFFFC7FFE3FFF301A
7F9933>I<0783F800FF8C1C00FF900E000FA0070007A0078007C0078007C00780078007
800780078007800780078007800780078007800780078007800780078007800780078007
8007800780078007800780078007800780078007800780078007800780FFFCFFFCFFFCFF
FC1E1A7F9921>I<007F000001C1C000070070000E0038001C001C003C001E003C001E00
78000F0078000F00F8000F80F8000F80F8000F80F8000F80F8000F80F8000F80F8000F80
F8000F8078000F0078000F003C001E003C001E001E003C000E0038000700700001C1C000
007F0000191A7E991E>I<0783F000FF8C1C00FFB00F0007A0078007C003C0078003E007
8001E0078001F0078001F0078000F8078000F8078000F8078000F8078000F8078000F807
8000F8078000F0078001F0078001F0078001E0078003C007C003C007C0078007A00E0007
983C000787E0000780000007800000078000000780000007800000078000000780000007
8000000780000007800000FFFC0000FFFC00001D267F9921>I<0787C0FF98E0FF91F00F
A1F007C1F007C0E007C00007800007800007800007800007800007800007800007800007
800007800007800007800007800007800007800007800007C000FFFE00FFFE00141A7F99
17>114 D<07F8401C06C03001C06000C06000C0E00040E00040F00040F800007E00007F
F0003FFE000FFF0003FF80003FC00007C08001E08001E0C000E0C000E0C000E0E000C0F0
01C0F80180C4070083F800131A7E9918>I<008000008000008000008000018000018000
0180000380000380000780000F80001FFF80FFFF80078000078000078000078000078000
078000078000078000078000078000078000078000078000078040078040078040078040
07804007804007804003C08001C08000E100003E0012257FA417>I
E end
%%EndProlog
%%BeginSetup
%%Feature: *Resolution 300dpi
TeXDict begin

%%EndSetup
%%Page: 1 1
1 0 bop 205 154 a Fr(13.)26 b(A)20 b(Prop)r(osal)f(for)h
(Garbage-Collector-Safe)f(C)h(Compilation)1724 132 y
Fq(\003)627 353 y Fp(Hans-J.)c(Bo)q(ehm)f(and)g(Da)o(vid)g(Chase)522
417 y Fo(Xero)o(x)g(P)m(AR)o(C)136 b(Sun)14 b(Microsystems,)g(Inc.,)f
(MS)h(12-40)435 467 y(3333)f(Co)o(y)o(ote)h(Hill)e(Road)176
b(2550)13 b(Garcia)g(Av)o(en)o(ue)452 517 y(P)o(alo)g(Alto,)g(CA)h
(94304)84 b(Moun)o(tain)13 b(View,)g(CA)h(94043-1100)561
567 y(\(Bo)q(ehm\))414 b(\(Chase\))884 723 y Fp(Abstract)104
790 y Fo(Conserv)n(ativ)o(e)9 b(garbage)h(collectors)g(are)g(commonly)c
(used)k(in)g(com)o(bination)d(with)i(con)o(v)o(en)o(tional)f(C)i
(programs.)104 840 y(Empirically)m(,)k(this)i(usually)g(w)o(orks)h(w)o
(ell.)26 b(Ho)o(w)o(ev)o(er,)18 b(there)g(are)f(no)f(guaran)o(tees)i
(that)f(this)g(is)f(safe)h(in)g(the)104 890 y(presence)d(of)e(\\impro)o
(v)o(ed")e(compiler)h(optimization.)k(W)m(e)c(prop)q(ose)i(that)g(C)f
(compilers)f(pro)o(vide)h(a)g(facilit)o(y)e(to)104 940
y(suppress)17 b(optimizations)c(that)i(are)h(unsafe)g(in)f(the)g
(presence)j(of)d(conserv)n(ativ)o(e)h(garbage)f(collection.)22
b(Suc)o(h)104 989 y(a)17 b(facilit)o(y)g(can)h(b)q(e)g(added)g(to)g(an)
g(existing)f(compiler)g(at)g(v)o(ery)h(minima)o(l)d(cost,)k(pro)o
(vided)f(the)g(additional)104 1039 y(analysis)f(is)g(done)h(in)f(a)h
(mac)o(hine-indep)q(enden)o(t)f(source-to-source)j(prepass.)31
b(Suc)o(h)18 b(a)f(prepass)i(ma)o(y)d(also)104 1089 y(c)o(hec)o(k)f
(the)f(source)h(co)q(de)g(for)f(garbage-collector-safet)o(y)m(.)0
1226 y Fn(Garbage)24 b(Collecti)o(on)d(and)i(C)0 1317
y Fo(C)15 b(programs)e(normally)g(allo)q(cate)h(dynamic)f(memory)f
(using)j Fm(malloc)p Fo(,)e(and)i(explicitly)f(deallo)q(cate)g(memory)f
(b)o(y)h(calling)0 1367 y Fm(free)g Fo(when)i(it)e(is)h(no)g(longer)f
(needed.)23 b(This)15 b(approac)o(h)g(is)g(simple)e(to)i(describ)q(e)i
(and)e(relativ)o(ely)f(simple)f(to)i(implemen)o(t.)0
1417 y(Both)j Fm(malloc)f Fo(and)h Fm(free)f Fo(can)h(b)q(e)h(implem)o
(en)o(ted)d(reasonably)i(e\016cien)o(tly)g(with)g(fairly)e(predictable)
j(execution)g(time.)0 1467 y(Ho)o(w)o(ev)o(er,)c(the)g(need)h(for)f
(explicit)f(deallo)q(cation)g(often)h(b)q(ecomes)g(cum)o(b)q(ersome)f
(for)g(programs)g(that)h(manipulate)d(com-)0 1516 y(plicated)j(link)o
(ed)g(structures.)24 b(W)m(orse)15 b(y)o(et,)g(explicit)g(deallo)q
(cation)f(can)h(substan)o(tially)g(complicate)e(in)o(terfaces)k(b)q(et)
o(w)o(een)0 1566 y(program)12 b(units,)i(and)g(is)f(lik)o(ely)g(to)h
(result)g(in)g(less)g(general)g(and)g(th)o(us)g(less)h(reusable)g(co)q
(de.)62 1616 y(T)m(o)c(illustrate)h(these)h(p)q(oin)o(ts,)f(consider)g
(the)h(implem)o(en)o(tation)c(of)i(a)g(general)h(\\stac)o(k)g(of)g
Fm(void)20 b(*)p Fo(")12 b(data)f(t)o(yp)q(e.)18 b(Assume)0
1666 y(w)o(e)10 b(implemen)o(t)d(stac)o(ks)k(as)f(link)o(ed)f(lists.)17
b(Eac)o(h)10 b(no)q(de)h(con)o(tains)f Fm(data)f Fo(and)h
Fm(next)f Fo(\014elds.)17 b(What)9 b(do)q(es)i(the)g(\\p)q(op")e(op)q
(eration)0 1716 y(do?)24 b(Presumably)15 b(it)g(returns)j(a)d(p)q(oin)o
(ter)h(to)g(all)e(but)j(the)f(\014rst)h(elemen)o(t)e(of)g(the)i(list.)
23 b(If)15 b(w)o(e)i(assume)e(the)h(op)q(eration)g(is)0
1765 y(allo)o(w)o(ed)e(to)i(destro)o(y)g(the)g(old)f(stac)o(k,)g(it)h
(will)e(deallo)q(cate)h(the)h(\014rst)g(link)o(ed)f(list)g(elemen)o(t)g
Fm(first)p Fo(.)22 b(Should)15 b(it)g(deallo)q(cate)0
1815 y Fm(first)21 b(->)g(data)p Fo(?)28 b(If)17 b(the)h(stac)o(k)g
(con)o(tains)f(p)q(oin)o(ters)h(to)g(data)f(not)g(otherwise)i
(referenced,)h(the)e(answ)o(er)g(is)g(\\y)o(es.")28 b(If)0
1865 y(it)16 b(p)q(oin)o(ts)h(to)g(en)o(tries)h(in)e(a)h(statically)f
(allo)q(cated)g(arra)o(y)m(,)h(the)g(answ)o(er)h(is)e(\\no.")27
b(If)16 b(it)g(p)q(oin)o(ts)h(to)g(separately)g(allo)q(cated)0
1915 y(ob)r(jects,)h(but)e(the)i(same)d(ob)r(ject)i(ma)o(y)e(b)q(e)i
(pushed)g(on)g(more)e(than)h(one)h(stac)o(k,)g(the)g(answ)o(er)g(is)g
(\\ma)o(yb)q(e.")24 b(Th)o(us)16 b(ev)o(en)0 1965 y(suc)o(h)e(a)f
(simple)e(abstraction)j(cannot)f(b)q(e)h(implemen)o(ted)d(with)h(a)h
(clean)h(in)o(terface;)f(w)o(e)h(m)o(ust)e(establish)h(some)f(con)o(v)o
(en)o(tion)0 2015 y(for)k(deallo)q(cation)e(whic)o(h)i(will)f(either)h
(complicate)f(the)h(in)o(terface)h(to)f(the)g(pac)o(k)n(age,)g(reduce)h
(its)f(applicabilit)o(y)m(,)e(or)h(force)0 2064 y(the)f(clien)o(t)g(to)
g(cop)o(y)g(ob)r(jects)h(unnecessarily)m(.)62 2114 y(The)i(need)g(for)e
(explicit)h(deallo)q(cation)f(mak)o(es)g(it)g(m)o(uc)o(h)g(more)g
(di\016cult)g(to)h(use)h(data)f(t)o(yp)q(e)g(implemen)o(tations)d(that)
0 2164 y(scale)e(w)o(ell)f(across)h(input)g(sizes,)h(suc)o(h)f(as)g
(link)o(ed)f(represen)o(tations)i(of)e(strings,)h(or)g(large)f(in)o
(tegers)i(represen)o(ted)h(b)o(y)d(p)q(oin)o(ters)0 2214
y(to)j(blo)q(c)o(ks)g(of)f(digits.)17 b(A)c(consequence)j(of)c(this)h
(is)g(that)g(C)g(programmers)e(are)i(encouraged)h(to)f(use)g(data)g
(represen)o(tations)0 2264 y(that)j(in)o(v)o(olv)o(e)f(few)h(p)q(oin)o
(ters.)26 b(This)16 b(results)h(in)f(either)h(excessiv)o(e)h(cop)o
(ying)e(of)f(data)h(\(e.g.,)g(strings)h(that)f(are)h(copied)f(or)0
2313 y Fm(realloc)p Fo(ed)f(whenev)o(er)i(they)g(outgro)o(w)e(a)h(con)o
(tiguous)f(region)h(of)f(storage\))i(or)f(arbitrary)g(size)g
(limitations)d(\(e.g.,)j(\014xed)0 2363 y(size)f(string)f(bu\013ers\).)
p 0 2400 780 2 v 46 2427 a Fl(\003)64 2439 y Fk(Reprin)o(ted)9
b(from)i Fj(The)h(Journal)e(of)i(C)g(Language)e(T)m(ranslation)p
Fk(,)f(V)m(olume)i(4,)h(Num)o(b)q(er)f(2,)g(Decem)o(b)q(er)f(1992,)g
(pages)h(126{141.)j(Cop)o(yrigh)o(t)10 2477 y(c)0 2478
y Fi(\015)p Fk(1992,)c(I.E.C.C.)965 2637 y Fo(1)p eop
%%Page: 2 2
2 1 bop 14 8 a Fo(2)952 b Fh(The)14 b(Journal)g(of)f(C)h(Language)f(T)m
(ranslation)g({)g(REPRINT)p 0 23 1950 2 v 62 154 a Fo(These)g(problems)
e(are)g(aggra)o(v)n(ated)g(b)o(y)g(the)h(fact)g(that)g(explicit)f
(deallo)q(cation)f(of)h(heap-allo)q(cated)g(memory)e(is)i(a)h(ma)r(jor)
0 203 y(source)j(of)f(time-consuming)d(errors.)20 b(Premature)14
b(deallo)q(cation)f(bugs)i(are)f(extremely)g(di\016cult)f(to)h(trace,)h
(in)e(that)i(their)0 253 y(symptoms)d(usually)i(do)h(not)f(app)q(ear)h
(un)o(til)f(the)i(cause)f(of)f(the)i(problem)d(is)i(no)f(longer)g
(visible.)20 b(An)15 b(arbitrary)g(program)0 303 y(mo)q(dule)g
Fg(A)i Fo(can)g(cause)h(arbitrary)e(failures)h(in)f(some)g(other)h(mo)q
(dule)e Fg(B)i Fo(b)o(y)g(deallo)q(cating)e(memory)g(and)h(then)i
(writing)0 353 y(in)o(to)c(it)h(after)g(it)g(has)g(b)q(een)i(reallo)q
(cated)e(b)o(y)g Fg(B)p Fo(.)g(This)g(mak)o(es)f(it)g(di\016cult)h(to)g
(debug)g(suc)o(h)h(problems)e(without)h(a)g(p)q(erson)0
403 y(who)f(understands)h(the)g(en)o(tire)f(system.)k(F)m(or)c(large)f
(systems,)h(there)h(is)f(usually)f(no)g(suc)o(h)i(p)q(erson.)62
452 y(The)i(situation)f(deteriorates)h(further)h(in)d(a)h(m)o
(ulti-threaded)f(en)o(vironmen)o(t,)h(b)q(oth)g(b)q(ecause)i(it)e(b)q
(ecomes)g(ev)o(en)h(less)0 502 y(clear)e(who)g(will)e(ha)o(v)o(e)i(the)
g(last)g(reference)i(to)e(an)f(ob)r(ject,)i(and)e(b)q(ecause)j(the)e
(resulting)g(problems)f(are)h(lik)o(ely)f(not)h(to)f(b)q(e)0
552 y(rep)q(eatable,)g(th)o(us)h(making)c(them)i(ev)o(en)i(harder)g(to)
e(trace.)62 602 y(Explicit)d(deallo)q(cation)f(is)i(completely)e
(unsatisfactory)h(if)g(C)g(is)h(used)g(as)f(an)h(in)o(termediate)e
(language)h(b)o(y)g(compilers)f(for)0 652 y(languages)i(that)g(require)
h(garbage)f(collection)g(\(e.g.,)g(Common)d(Lisp)j([16)o(]\),)g(Sc)o
(heme)h([4)o(,)f(14)o(],)g(ML)g(\(cf.)18 b([8)o(]\),)11
b(Cedar/Mesa)0 702 y([2)o(],)i(or)h(Sather)h([13)o(]\).)62
751 y(A)g(garbage)f(collecting)g(storage)h(allo)q(cator)f(solv)o(es)g
(these)i(problems.)j(The)c(clien)o(t)g(program)e(still)g(allo)q(cates)h
(memory)0 801 y(using)i(a)h(routine)g(equiv)n(alen)o(t)f(to)g
Fm(malloc)p Fo(.)25 b(In)17 b(this)f(pap)q(er,)i(w)o(e)f(will)e(still)h
(call)f(it)i Fm(malloc)p Fo(.)25 b(Ho)o(w)o(ev)o(er,)17
b(it)f(is)h(no)f(longer)0 851 y(necessary)c(to)e(call)f
Fm(free)p Fo(.)16 b(The)10 b(garbage)g(collector)g(\(GC\))g(will)e(run)
i(p)q(erio)q(dically)m(,)f(either)i(as)f(part)g(of)f(a)h
Fm(malloc)f Fo(in)o(v)o(o)q(cation,)0 901 y(or)j(async)o(hronously)g
(in)f(a)g(separate)i(thread,)f(and)g(reclaim)e(memory)f(that)j(it)g
(can)f(determine)h(will)e(no)i(longer)f(b)q(e)i(accessed)0
951 y(b)o(y)i(the)g(clien)o(t)g(co)q(de,)h(b)q(ecause)h(it)d(can)h(no)g
(longer)g(b)q(e)g(reac)o(hed)i(b)o(y)d(follo)o(wing)f(a)h(c)o(hain)h
(of)f(p)q(oin)o(ters.)22 b(Conceptually)m(,)14 b(the)0
1000 y(garbage)g(collector)g(then)g(in)o(v)o(ok)o(es)g
Fm(free)f Fo(on)g(all)g(suc)o(h)i(memory)c(to)j(again)e(mak)o(e)h(it)g
(a)o(v)n(ailable)f(for)i(allo)q(cation.)62 1050 y(There)j(are)f(a)f(n)o
(um)o(b)q(er)f(of)h(p)q(erformance)g(reasons)i(not)e(to)g(implemen)o(t)
e(a)i(garbage)g(collector)g(on)g(top)h(of)e(a)i(standard)0
1100 y Fm(malloc)p Fo(/)p Fm(free)c Fo(implemen)o(tation.)17
b(Because)g(garbage)d(collectors)h(deallo)q(cate)g(ob)r(jects)h(in)e
(bulk)g(and)h(generate)h(informa-)0 1150 y(tion)e(ab)q(out)h(the)h
(state)f(of)f(the)i(en)o(tire)g(heap,)e(they)i(can)f(realize)g
(signi\014can)o(t)g(p)q(erformance)f(adv)n(an)o(tages)h(o)o(v)o(er)g
(ob)r(ject-at-)0 1200 y(a-time)c(deallo)q(cation.)17
b(Garbage)12 b(collection)g(is)h(usually)f(comp)q(etitiv)o(e)g(with)g
(explicit)h(deallo)q(cation)e(in)i(o)o(v)o(erall)e(execution)0
1249 y(time.)28 b(Some)16 b(empirical)g(comparisons)g(of)h(the)i(p)q
(erformance)e(of)g(garbage)g(collection)h(and)f(explicit)g(deallo)q
(cation)g(are)0 1299 y(giv)o(en)12 b(in)h([17)o(].)232
1284 y Ff(1)267 1299 y Fo(But)h(for)e(the)h(purp)q(oses)i(of)d(this)h
(pap)q(er,)g(the)g(reader)h(ma)o(y)d(assume)h(that)h(the)h(collector)f
(is)f(simply)f(a)h(la)o(y)o(er)0 1349 y(on)i(top)f(of)h(a)f
Fm(malloc)p Fo(/)p Fm(free)f Fo(implemen)o(tatio)o(n)f(that)j
(automatically)d(p)q(erforms)i Fm(free)g Fo(calls.)62
1399 y(T)m(raditional)8 b(garbage)i(collectors)h(require)g(data)f
(structure)j(la)o(y)o(out)c(information,)e(so)k(that)f(accessible)i
(data)d(structures)0 1449 y(can)16 b(b)q(e)h(tra)o(v)o(ersed)g(and)f
(iden)o(ti\014ed.)24 b(Conserv)n(ativ)o(e)16 b(garbage)g(collectors)g
(a)o(v)o(oid)f(this)h(requiremen)o(t)g(b)o(y)g(treating)g(all)e(bit)0
1499 y(patterns)h(that)f(could)g(conceiv)n(ably)f(represen)o(t)j(p)q
(oin)o(ters)f(as)f(p)q(oin)o(ters)g([6)o(].)62 1548 y(On)f(a)g(t)o
(ypical)f(32)g(bit)g(RISC)g(w)o(orkstation,)g(a)h(v)o(ery)g(naiv)o(e)f
(\(and)g(v)o(ery)h(ine\016cien)o(t\))g(collector)g(migh)o(t)e(w)o(ork)h
(as)h(follo)o(ws.)0 1598 y(When)h Fm(malloc)f Fo(allo)q(cates)g(an)h
(ob)r(ject,)g(it)g(adds)g(it)f(to)h(a)g(hash)g(table)g(of)f(allo)q
(cated)g(ob)r(jects.)20 b(When)14 b(it)f(disco)o(v)o(ers)i(there)g(is)0
1648 y(no)g(space)i(a)o(v)n(ailable,)d(it)h(sets)i(a)e(mark)f(bit)i
(asso)q(ciated)g(with)g(eac)o(h)g(ob)r(ject)g(that)g(ma)o(y)e(still)g
(b)q(e)j(in)e(use.)24 b(It)16 b(do)q(es)g(this)g(b)o(y)0
1698 y(lo)q(oking)d(at)h(eac)o(h)h(of)f(the)h(pro)q(cessor)i
(registers,)f(eac)o(h)f(w)o(ord)f(in)g(the)h(stac)o(k,)g(and)f(eac)o(h)
h(w)o(ord)g(in)f(the)h(statically)e(allo)q(cated)0 1748
y(data)f(areas.)18 b(Whenev)o(er)c(one)e(of)g(these)i(con)o(tains)e
(the)i(address)f(of)f(an)g(unmark)o(ed)g(ob)r(ject)h(\(to)f(b)q(e)h
(de\014ned)h(more)d(carefully)0 1797 y(later\),)19 b(the)g(mark)d(bit)i
(of)g(that)g(ob)r(ject)h(is)f(set,)i(and)e(eac)o(h)g(w)o(ord)g(in)g
(the)h(ob)r(ject)g(is)f(recursiv)o(ely)h(scanned)g(for)f(further)0
1847 y(p)q(oin)o(ters.)h(Finally)12 b(the)i(hash)g(table)g(is)g(tra)o
(v)o(ersed)h(and)f(unmark)o(ed)f(ob)r(jects)i(are)f(deallo)q(cated.)62
1897 y(Since)j(the)f(collector)g(do)q(esn't)g(distinguish)f(p)q(oin)o
(ters)i(from)d(other)i(data,)g(it)f(ma)o(y)f(o)q(ccasionally)h(mark)f
(ob)r(jects)j(that)0 1947 y(are)e(in)g(fact)g(unreac)o(hable.)22
b(This)15 b(ma)o(y)e(o)q(ccasionally)h(result)h(in)g(reten)o(tion)g(of)
g(more)f(memory)e(than)j(with)g(a)f(traditional)0 1997
y(collector.)j(Empirically)m(,)9 b(this)i(is)g(rarely)g(observ)n(able)g
(in)g(a)g(w)o(ell-designed)g(system)g(running)g(in)f(a)h(32-bit)f(or)i
(larger)f(address)0 2046 y(space)18 b([6].)27 b(Clev)o(er)18
b(allo)q(cators)e(can)i(reduce)h(suc)o(h)f(reten)o(tion)g(dramatically)
c(b)o(y)j(not)g(allo)q(cating)f(ob)r(jects)i(at)f(lo)q(cations)0
2096 y(that)d(are)g(lik)o(ely)f(to)h(b)q(e)g(p)q(oin)o(ted)g(to)g(b)o
(y)f(in)o(tegers)i(and)f(the)g(lik)o(e.)62 2146 y(Conserv)n(ativ)o(e)j
(garbage)e(collection)h(is)g(an)g(appropriate)g(to)q(ol)g(for)g(a)g
(large)f(fraction)h(of)g(C)g(co)q(de.)25 b(It)17 b(is)f(particularly)0
2196 y(appropriate)10 b(for)g(traditional)f(compilers)g(and)h(similar)e
(applications,)h(where)i(the)g(main)d(p)q(erformance)i(criterion)h(is)f
(o)o(v)o(erall)0 2246 y(elapsed)j(time.)j(Garbage)11
b(collection)h(usually)f(do)q(es)i(not)f(imp)q(ose)e(a)i(signi\014can)o
(t)g(p)q(enalt)o(y)f(in)h(o)o(v)o(erall)f(execution)i(time,)d(and)0
2296 y(ma)o(y)j(pro)o(vide)j(a)f(gain,)f(esp)q(ecially)h(when)h(the)g
(accoun)o(ting)f(includes)h(extra)g(cop)o(ying)f(and)g(other)h(o)o(v)o
(erhead)f(for)g(explicit)0 2345 y(deallo)q(cation.)i(Ho)o(w)o(ev)o(er)e
(it)e(do)q(es)i(imp)q(ose)e(t)o(w)o(o)g(kinds)h(of)f(p)q(enalties.)19
b(It)14 b(ma)o(y)e(require)j(more)e(space,)i(since)f(a)g(completely)p
0 2380 780 2 v 46 2407 a Fe(1)64 2419 y Fk(The)e(reader)f(is)i
(encouraged)d(to)i(mak)o(e)g(his/her)f(o)o(wn)h(comparisons.)k(A)e(new)
o(er)e(v)o(ersion)f(of)i(the)f(collector)e(describ)q(ed)g(there)i(is)h
(a)o(v)n(ailable)0 2458 y(for)e(anon)o(ymous)d(FTP)13
b(from)d(parcftp.xero)n(x.c)o(om)o(:)j(pub/russell/g)o(c.t)o(ar.Z)p
eop
%%Page: 3 3
3 2 bop 14 8 a Fh(A)14 b(Prop)q(osal)g(for)f(GC-Safe)g(C)h(Compilation)
d(|)i(Bo)q(ehm)g(and)h(Chase)802 b Fo(3)p 0 23 1950 2
v 0 154 a(full)14 b(heap)i(w)o(ould)e(cause)i(excessiv)o(ely)h(frequen)
o(t)f(collections.)22 b(And)16 b(it)f(ma)o(y)e(force)j(the)g(clien)o(t)
f(program)f(to)h(p)q(erio)q(dically)0 203 y(pause)g(for)e(a)h
(collection.)62 253 y(P)o(auses)20 b(for)e(garbage)g(collection)h
(generally)f(prev)o(en)o(t)h(the)h(use)f(of)f(conserv)n(ativ)o(e)h
(collection)f(with)h(programs)e(that)0 303 y(in)o(v)o(olv)o(e)12
b(hard)i(real-time)e(constrain)o(ts.)18 b(\(But)d(note)e(that)h
Fm(malloc)p Fo(/)p Fm(free)d Fo(is)i(also)g(problematic)f(in)h(suc)o(h)
i(a)e(con)o(text.\))19 b(It)13 b(is)0 353 y(usually)g(not)g(a)g
(problem)f(for)h(in)o(teractiv)o(e)h(applications.)j(V)m(ery)d(straigh)
o(tforw)o(ard)f(collectors)h(can)f(tra)o(v)o(erse)i(on)e(the)h(order)0
403 y(of)i(3)h(MBytes)h(of)e(data)h(p)q(er)g(second)h(on)f(a)f(SP)m(AR)
o(Cstation)g(2.)27 b(With)16 b(a)g(more)g(sophisticated)i(collector)f
(and)f(minima)o(l)0 452 y(op)q(erating)f(system)h(supp)q(ort,)g
(latencies)g(can)g(b)q(e)g(reduced)h(to)f(the)g(order)g(of)f(100)g
(milliseconds)f(on)h(the)h(same)f(mac)o(hine,)0 502 y(largely)j(indep)q
(enden)o(t)h(of)f(heap)h(size)g([5)o(].)31 b(Th)o(us)19
b(garbage)f(collectors)h(can)g(meet)f(resp)q(onse)i(requiremen)o(ts)f
(similar)d(to)0 552 y(those)e(of)f(virtual)g(memory)e(systems.)19
b(Still)12 b(smaller)g(latencies)j(can)e(b)q(e)i(obtained)e(\(at)h
(some)f(cost)h(in)f(con)o(v)o(enience\))i(with)0 602
y(deferred)h(reference)g(coun)o(t)e(collectors)h([9)o(].)62
652 y(Ev)o(en)f(if)f(explicit)g(storage)h(managemen)o(t)d(is)i(c)o
(hosen)i(for)e(the)h(\014nal)f(v)o(ersion)h(of)f(a)g(program,)e
(garbage)j(collection)f(ma)o(y)0 702 y(b)q(e)h(used)g(in)f(to)q(ols)g
(suc)o(h)h(as)f(Purify)g([12)o(])g(to)g(iden)o(tify)f(storage)i(leaks)f
([6].)k(The)d(concerns)h(b)q(elo)o(w)e(also)f(apply)m(,)g(though)h(to)g
(a)0 751 y(lesser)i(exten)o(t,)g(to)e(suc)o(h)i(systems.)0
889 y Fn(GC-Safe)23 b(Compilation)0 980 y Fo(Empirically)m(,)8
b(there)j(is)g(rarely)f(a)g(problem)g(with)g(using)g(con)o(v)o(en)o
(tional)f(C)i(compilers)e(in)h(com)o(bination)e(with)i(a)g(conserv)n
(ativ)o(e)0 1029 y(collector.)19 b(W)m(ell)12 b(o)o(v)o(er)i(a)g
(million)d(lines)j(of)f(Cedar/Mesa)i(co)q(de)g(ha)o(v)o(e)f(b)q(een)h
(compiled)d(to)i(C)g(and)g(run)g(without)g(di\016cult)o(y)0
1079 y(in)f(this)h(w)o(a)o(y)m(.)62 1129 y(Ho)o(w)o(ev)o(er,)d(the)g
(ANSI)f(C)g(standard)h([1)o(])f(do)q(es)h(not)f(preclude)h
(optimizations)d(that)i(are)h(unsafe)f(in)g(this)g(con)o(text.)17
b(Indeed,)0 1179 y(curren)o(t)f(C)f(compiler)e(optimizations)f(are)k
(often)e(unsafe)h(in)g(the)g(presence)i(of)d(garbage)h(collection,)f
(though)g(only)g(under)0 1229 y(unlik)o(ely)f(circumstances.)62
1278 y(T)m(o)g(illustrate)h(the)g(problem,)f(consider)h(the)h(lo)q(op)e
(in)g(a)h(co)q(de)h(fragmen)o(t)d(as)i(compiled)e(to)i(a)g(SP)m(AR)o(C)
f(pro)q(cessor:)104 1370 y Fm(int)21 b(f\(\))104 1420
y Fq(f)191 1469 y Fm(int)g(*a,)g(*b;)191 1519 y(int)g(i,)h(sum;)191
1569 y(a)g(=)f(\(int)g(*\))g(malloc\(100000)f(*)h(sizeof)g(\(int\)\);)
191 1619 y(b)h(=)f(\(int)g(*\))g(malloc\(100000)f(*)h(sizeof)g
(\(int\)\);)191 1669 y(...)191 1718 y(for)g(\(i)h(=)f(0;)g(i)h(<)g
(100000;)e(i++\))h Fq(f)278 1768 y Fm(sum)g(+=)h(a[i])f(+)g(b[i];)191
1818 y Fq(g)191 1868 y Fm(return\(sum\);)104 1918 y Fq(g)62
1988 y Fo(whic)o(h)14 b(could)g(pro\014tably)f(b)q(e)i(compiled)d(to)i
(something)e(lik)o(e:)104 2080 y Fm(diff)21 b(=)g(b-a;)104
2129 y(/*)g(diff)g(reuses)g(b's)g(register,)f(which)h(is)g(now)g(dead.)
g(*/)104 2179 y(for\(aptr)f(=)i(a;)f(aptr)g(<)g(a)h(+)g(100000;)e
(a++\))h Fq(f)191 2229 y Fm(sum)g(+=)h(*aptr)e(+)i(*\(aptr+diff\);)104
2279 y Fq(g)62 2349 y Fo(\(This)12 b(is)g(pro\014table)h(on)e(a)h(SP)m
(AR)o(C)g(b)q(ecause)h(the)g Fm(aptr+diff)d Fo(addition)h(is)h(free,)h
(since)g(it)f(b)q(ecomes)g(part)g(of)g(a)g(doubly)0 2399
y(indexed)i(load)f(instruction.)19 b(This)13 b(stun)o(t)i(sa)o(v)o(es)f
(an)g(incremen)o(t)g(instruction)g(in)f(the)i(lo)q(op,)d(and)i(no)g
(shift)f(op)q(erations)i(are)0 2449 y(necessary)m(.\))20
b(The)13 b(result)h(is)g(that)f Fm(b)g Fo(do)q(es)h(not)f(app)q(ear)h
(accessible)h(to)e(a)g(garbage)g(collection)g(o)q(ccurring)h(inside)f
(the)h(lo)q(op.)0 2499 y(\(In)g(a)g(single)f(threaded)i(system,)e(w)o
(e)i(w)o(ould)e(need)h(a)g(function)g(call)f(inside)h(the)g(lo)q(op)f
(to)h(trigger)g(the)g(collection.\))p eop
%%Page: 4 4
4 3 bop 14 8 a Fo(4)952 b Fh(The)14 b(Journal)g(of)f(C)h(Language)f(T)m
(ranslation)g({)g(REPRINT)p 0 23 1950 2 v 62 154 a Fo(Curren)o(t)21
b(SP)m(AR)o(C)e(compilers)g(do)g(not)h(app)q(ear)g(to)f(pro)q(duce)i
(suc)o(h)g(co)q(de)f(for)f(this)h(example.)34 b(Ho)o(w)o(ev)o(er,)21
b(simpler)0 203 y(v)o(ersions)14 b(of)f(the)h(problem)f(do)g(app)q(ear)
h(in)f(other)i(con)o(texts)f(and)g(on)f(other)i(mac)o(hines.)i
(Consider)d(the)g(function)f Fm(f)h Fo(in)f(this)0 253
y(fragmen)o(t:)104 328 y Fm(struct)20 b(s)i Fq(f)191
378 y Fm(char)f(space[35000];)191 427 y(struct)g(s)g(*)h(next;)104
477 y Fq(g)p Fm(;)104 577 y(struct)e(s)i(*)g(f\(x\))104
627 y(struct)e(s)i(*)g(x;)104 676 y Fq(f)191 726 y Fm(return\(x)e(->)h
(next\);)104 776 y Fq(g)62 847 y Fo(On)16 b(an)f(IBM)g(RISC)g
(System/6000,)f(this)h(results)h(in)f(the)h(follo)o(wing)c(co)q(de)17
b(\(extracted)f(from)e(a)h(compiler)f(pro)q(duced)0 896
y(listing\):)104 971 y Fm(AIU)130 b(r3=r3,1)104 1021
y(L)174 b(r3=SHADOW$\(r3,-30)o(536\))104 1071 y(BA)152
b(lr)62 1141 y Fo(The)14 b(\014rst)f(instruction)g(adds)g(1)g(to)g(the)
g(upp)q(er)h(half)e(of)g(the)h(argumen)o(t.)k(If)12 b(a)h(garbage)g
(collection)f(is)h(triggered)g(at)g(this)0 1191 y(p)q(oin)o(t,)f(e.g.,)
f(b)o(y)h(a)g(concurren)o(t)i(thread,)f(the)g(only)e(reference)k(to)d
Fm(x)g Fo(consists)i(of)d Fm(x)22 b(+)f(65536)12 b Fo(stored)h(in)f
Fm(r3)p Fo(.)17 b(The)c(follo)o(wing)0 1241 y(load)g(instruction)h
(then)h(supplies)f(an)g(o\013set)g(of)g Fm(-30536)e Fo(to)i(comp)q
(ensate)g(for)g(the)g(initial)e(o)o(v)o(ersho)q(ot.)62
1291 y(Optimizations)h(on)i(arra)o(y)f(index)h(expressions)i(can)e
(also)f(result)i(in)e(a)g(situation)h(in)f(whic)o(h)h(the)g(only)f
(reference)k(to)c(a)0 1340 y(heap)f(allo)q(cated)f(arra)o(y)g(main)o
(tained)e(during)i(the)h(arra)o(y)f(access)i(is)e(an)h(address)g(w)o
(ell)f(outside)h(the)g(ob)r(ject.)18 b(T)o(ypically)11
b(this)0 1390 y(do)q(es)17 b(not)e(cause)i(problems,)e(since)i(there)g
(are)g(other)f(references)j(to)d(an)f(arra)o(y)m(.)24
b(But)16 b(there)h(is)f(no)g(guaran)o(tee)g(that)g(this)0
1440 y(will)c(b)q(e)j(the)f(case.)62 1490 y(Giv)o(en)19
b(curren)o(t)h(compilers,)f(the)h(only)f(w)o(a)o(ys)f(to)i(a)o(v)o(oid)
d(suc)o(h)j(problems)f(are)g(to)g(disable)g(optimization,)e(to)i(force)
0 1540 y(p)q(oin)o(ters)f(suc)o(h)g(as)f Fm(a)p Fo(,)g
Fm(b)p Fo(,)g(or)g Fm(x)g Fo(to)g(memory)e(b)o(y)h(declaring)h(them)g
(as)g(v)o(olatile,)f(or)h(b)o(y)g(explicitly)f(storing)h(them)f(in)o
(to)g(a)0 1589 y(global)h(data)i(structure,)i(th)o(us)f(e\013ectiv)o
(ely)f(registering)h(them)e(as)h(ro)q(ots)g(for)f(the)i(garbage)e
(collector.)34 b(The)19 b(\014rst)g(t)o(w)o(o)0 1639
y(alternativ)o(es)g(can)h(b)q(e)f(extraordinarily)g(exp)q(ensiv)o(e,)i
(esp)q(ecially)e(on)g(mo)q(dern)f(arc)o(hitectures.)36
b(The)20 b(third)f(alternativ)o(e)0 1689 y(requires)c(a)f(substan)o
(tial)g(prepro)q(cessor)i(of)e(some)f(sort.)19 b(It)14
b(is)g(less)g(costly)h(than)f(the)g(previous)h(alternativ)o(es)f(in)f
(this)h(case.)0 1739 y(But)g(it)g(app)q(ears)g(di\016cult)g(to)f(b)q
(oth)h(automate)f(it)g(and)h(to)f(k)o(eep)i(the)f(costs)h(do)o(wn)e(in)
h(all)e(cases.)20 b(Explicit)13 b(registration)h(of)0
1789 y(ev)o(ery)f(lo)q(cal)e(p)q(oin)o(ter)h(v)n(ariable)f(is)h(to)q(o)
g(exp)q(ensiv)o(e)h(for)e(man)o(y)g(applications)g([11)o(].)16
b(An)o(ything)c(else)h(ma)o(y)d(require)j(non)o(trivial)0
1838 y(analysis)g(of)g(the)i(en)o(tire)f(program.)62
1888 y(This)g(prop)q(osal)g(is)h(in)o(tended)g(to)f(optionally)e(limit)
g(C)i(compiler)f(optimizations)f(to)i(guaran)o(tee)h(safet)o(y)f(for)g
(collectors)0 1938 y(suc)o(h)19 b(as)g(those)g(describ)q(ed)h(in)e([6)o
(],)h([3)o(],)g(and)f([5].)31 b(The)19 b(mostly)d(cop)o(ying)i
(collector)h(of)f([3)o(])g(further)h(requires)h(either)f(a)0
1988 y(prepro)q(cessor)h(or)d(programmer)e(discipline)i(to)g(iden)o
(tify)g(p)q(oin)o(ters)h(in)e(heap)i(ob)r(jects.)29 b(This)18
b(prop)q(osal)f(should)g(also)f(b)q(e)0 2038 y(su\016cien)o(t)k(to)f
(allo)o(w)f(a)h(safe,)h(prepro)q(cessor-based)i(implemen)o(tation)16
b(of)j(dela)o(y)o(ed)g(reference)j(coun)o(ting)d(\(cf.)34
b([15)o(,)19 b(9]\).)0 2088 y(W)m(e)e(do)g(not)g(address)h(the)g(more)e
(di\016cult)g(problem)g(of)g(supp)q(orting)i(collectors)f(that)h(can)f
(mo)o(v)o(e)e(all)h(ob)r(jects)j(in)d(order)0 2137 y(to)h(compact)e
(the)j(heap.)27 b(F)m(or)16 b(a)g(discussion)i(of)e(ho)o(w)g(to)g
(accomplish)g(this)g(for)h(a)f(language)g(that)h(pro)o(vides)g(more)e
(t)o(yp)q(e)0 2187 y(information)c(than)j(C,)f(see)i([10)o(].)62
2237 y(The)g(discussion)f(here)h(assumes)f(C)g(source)h(co)q(de.)k
(Nearly)14 b(all)e(of)i(it)f(is)h(equally)f(applicable)g(to)h(C)p
Fm(++)p Fo(.)0 2371 y Fn(Base)23 b(P)n(oin)n(ters)f(and)i(Deriv)n(ed)e
(P)n(oin)n(ters)0 2462 y Fo(W)m(e)15 b(de\014ne)h(an)o(y)f(p)q(oin)o
(ter)h(v)n(alue)e(directly)i(recognizable)g(b)o(y)f(the)h(garbage)f
(collector)g(to)g(b)q(e)h(a)f Fg(b)n(ase)i(p)n(ointer)p
Fo(.)22 b(The)16 b(v)n(alue)0 2512 y(returned)e(b)o(y)d(an)h(allo)q
(cation)f(function)g(\(e.g.,)h Fm(malloc)p Fo(\))e(is)i(a)g(base)g(p)q
(oin)o(ter.)18 b(A)12 b(base)h(p)q(oin)o(ter)f(is)g(not)g(necessarily)h
(the)f(base)p eop
%%Page: 5 5
5 4 bop 14 8 a Fh(A)14 b(Prop)q(osal)g(for)f(GC-Safe)g(C)h(Compilation)
d(|)i(Bo)q(ehm)g(and)h(Chase)802 b Fo(5)p 0 23 1950 2
v 0 154 a(address)14 b(of)f(an)f(ob)r(ject,)i(but)f(the)h(garbage)f
(collector)g(m)o(ust)f(b)q(e)h(able)g(to)g(easily)g(con)o(v)o(ert)g(it)
g(to)g(one.)18 b(\(F)m(or)12 b(example,)g(man)o(y)0 203
y(standard)j Fm(malloc)e Fo(implem)o(en)o(tations)f(store)j(b)q(o)q
(okk)o(eeping)f(information)e(at)i(the)h(b)q(eginning)e(of)h(an)g(ob)r
(ject,)h(and)f(return)0 253 y(a)i(displaced)g(p)q(oin)o(ter.)24
b(A)16 b(Sc)o(heme)g(implemen)o(tatio)o(n)d(migh)o(t)h(add)i(one)g(to)g
(a)f(p)q(oin)o(ter)h(to)g(distinguish)f(it)h(from)e(a)i(30-)f(or)0
303 y(31-bit)e(in)o(teger.\))62 353 y(The)k(rest)g(of)f(this)h(prop)q
(osal)e(is)i(indep)q(enden)o(t)g(of)f(the)h(precise)h(de\014nition)e
(of)f(a)h(base)h(p)q(oin)o(ter,)g(since)g(that)f(dep)q(ends)0
403 y(on)i(the)g(particular)g(st)o(yle)g(of)f(garbage)h(collector.)30
b(As)18 b(illustrations,)g(w)o(e)g(will)e(refer)j(to)f(t)o(w)o(o)g(p)q
(ossibilities.)29 b(First,)19 b(w)o(e)0 452 y(iden)o(tify)14
b(a)g Fg(r)n(estrictive)e Fo(base)j(p)q(oin)o(ter)g(de\014nition,)f(in)
g(whic)o(h)g(only)g(p)q(oin)o(ter)g(v)n(alues)g(returned)i(b)o(y)f
Fm(malloc)e Fo(\(or)h Fm(realloc)p Fo(\))0 502 y(are)d(considered)h(to)
f(b)q(e)g(v)n(alid)e(base)i(p)q(oin)o(ters.)18 b(This)10
b(has)h(the)g(adv)n(an)o(tage)f(that)h(there)h(is)e(a)h(lo)o(w)e
(probabilit)o(y)g(of)i(acciden)o(tally)0 552 y(misiden)o(tifying)g
(non-p)q(oin)o(ter)k(data)e(as)i(p)q(oin)o(ters,)f(and)g(th)o(us)h
(unnecessarily)h(retaining)e(memory)m(.)i(Second,)f(w)o(e)f(consider)0
602 y(a)g Fg(lib)n(er)n(al)j Fo(base)e(p)q(oin)o(ter)g(de\014nition,)f
(in)f(whic)o(h)i(a)f(p)q(oin)o(ter)g(to)h(an)o(y)f(p)q(osition)f
(inside)i(an)f(ob)r(ject,)h(or)f(to)g(one)h(past)f(the)h(end)0
652 y(of)i(the)h(ob)r(ject,)i(is)d(considered)i(a)f(v)n(alid)e(base)i
(p)q(oin)o(ter.)30 b(This)18 b(requires)h(somewhat)d(more)h
(sophisticated)i(supp)q(ort)f(b)o(y)0 702 y(the)f(collector)f(and)g
(allo)q(cator)f(to)h(b)q(e)g(practical,)g(and)g(ma)o(y)e(require)j
(more)e(memory)m(.)22 b(But)16 b(it)g(has)g(the)h(adv)n(an)o(tage)e
(that)0 751 y(otherwise)g(arbitrary)f(C)f(programs)g(that)h(strictly)g
(conform)f(to)g([1])g(can)h(b)q(e)h(used)f(with)g(a)g(garbage)f
(collector.)62 801 y(In)o(termediate)i(base)g(p)q(oin)o(ter)g
(de\014nitions)g(are)g(common)d(and)j(quite)g(useful.)21
b(It)15 b(is)g(also)f(common)e(to)j(treat)g(p)q(oin)o(ters)0
851 y(originating)d(in)h(the)i(stac)o(k)f(or)g(registers)h(more)e(lib)q
(erally)g(than)h(the)g(notion)f(of)h(base)g(p)q(oin)o(ter)g(used)h
(elsewhere.)20 b(This)14 b(can)0 901 y(reduce)i(the)g(c)o(hances)g(of)e
(a)g(p)q(oin)o(ter)h(b)q(eing)f(hidden)h(b)o(y)g(a)f(compiler)f
(optimization,)f(but)j(it)f(can't)g(eliminate)f(it.)20
b(Neither)0 951 y(of)13 b(these)j(v)n(ariations)c(has)i(m)o(uc)o(h)f
(e\013ect)i(on)f(this)g(discussion.)62 1000 y(W)m(e)f(prop)q(ose)h
(that)f(the)g(C)g(compiler)f(remain)g(ignoran)o(t)g(of)g(the)i(base)g
(p)q(oin)o(ter)f(de\014nition.)k(It)c(will)f(ho)o(w)o(ev)o(er)h(b)q(e)h
(useful)0 1050 y(to)g(in)o(tro)q(duce)104 1142 y Fm(#)21
b(pragma)g(base)p 391 1142 14 2 v 15 w(pointer)12 b Fo(\()i
Fg(list)g(of)h(identi\014ers)28 b Fo(\))0 1233 y(to)16
b(indicate)h(that)g(either)g(the)g(giv)o(en)f(v)n(ariables)g(con)o
(tain)g(base)i(p)q(oin)o(ters)f(at)f(this)h(p)q(oin)o(t,)f(or)h(that)g
(the)g(giv)o(en)f(functions)0 1283 y(return)f(base)g(p)q(oin)o(ter)f(v)
n(alues.)19 b(This)14 b(mak)o(es)f(it)h(p)q(ossible)g(to)g(inform)e
(the)j(compiler)d(that)i(functions)h(lik)o(e)e Fm(malloc)g
Fo(return)0 1333 y(base)h(p)q(oin)o(ters)h(with)f(just)g(a)f(header)i
(\014le)f(declaration.)62 1382 y(W)m(e)f(ma)o(y)d(p)q(erform)i
(arithmetic)g(or)g(logical)f(op)q(erations)i(on)f(a)h(base)g(p)q(oin)o
(ter)g(to)f(deriv)o(e)h(another)g(v)n(alue)f(that)h(ma)o(y)e(still)0
1432 y(b)q(e)16 b(used)h(to)f(dereference)i(the)f(original)d(ob)r
(ject.)24 b(The)16 b(resulting)g(v)n(alue)f(ma)o(y)f(still)h(b)q(e)h(a)
g(base)g(p)q(oin)o(ter)g(\(the)g(usual)g(case)0 1482
y(under)e(the)f(lib)q(eral)f(de\014nition\))h(or)g(it)f(ma)o(y)f(no)i
(longer)f(b)q(e)i(recognizable)f(b)o(y)g(the)g(collector,)g(and)g(th)o
(us)g(b)q(ecome)g(a)f(deriv)o(ed)0 1532 y(p)q(oin)o(ter)17
b(\(the)g(usual)g(case)g(under)h(the)f(restrictiv)o(e)h
(de\014nition\).)26 b(An)o(y)17 b(v)n(alue)f(computed)g(from)f(a)h
(deriv)o(ed)h(p)q(oin)o(ter)g(and)0 1582 y(that)e(ma)o(y)d(still)i(b)q
(e)h(used)g(to)f(access)j(the)e(ob)r(ject)g(is)f(also)g(a)g(deriv)o(ed)
h(p)q(oin)o(ter.)20 b(\(This)15 b(is)f(true)i(ev)o(en)f(if)e(its)i(v)n
(alue)f(b)q(ecomes)0 1631 y(iden)o(tical)j(to)h(a)f(base)i(p)q(oin)o
(ter)f(to)f(the)i(ob)r(ject.)31 b(This)17 b(asp)q(ect)i(of)f(the)g
(de\014nition)f(is)h(unimp)q(ortan)o(t)e(to)i(the)g(clien)o(t,)h(but)0
1681 y(simpli\014es)12 b(the)j(task)f(of)f(GC-pro)q(o\014ng)g(existing)
h(compilers.\))0 1818 y Fn(GC-Safe)23 b(C)f(Programs)0
1909 y Fo(A)o(t)14 b(an)o(y)f(particular)h(p)q(oin)o(t)f(of)h
(execution)g(in)g(a)f(C)h(function)g Fm(f)p Fo(,)f(w)o(e)h(de\014ne)h
(the)f Fg(lo)n(c)n(al)h(r)n(o)n(ot)f(set)g Fo(to)g(b)q(e)g(the)h(set)f
(of)51 2001 y(1.)20 b(In-scop)q(e)15 b Fm(auto)e Fo(and)g
Fm(register)g Fo(v)n(ariables)g(declared)i(in)e Fm(f)h
Fo(and)f(visible)h(at)f(the)i(p)q(oin)o(t)e(of)h(execution.)51
2084 y(2.)20 b(All)d(previously)g(computed)g(v)n(alues)h(of)f(direct)i
(sub)q(expressions)g(of)f(incompletely)e(ev)n(aluated)h(expressions.)31
b(F)m(or)104 2134 y(example,)8 b(if)h(w)o(e)g(are)h(ab)q(out)f(to)g(p)q
(erform)g(the)h(addition)e(in)h Fm(\(char)20 b(*\))i(malloc\(N\))e(+)h
(4)p Fo(,)10 b(then)g(the)g(v)n(alue)e(computed)104 2183
y(b)o(y)13 b Fm(\(char)21 b(*\))h(malloc\(N\))12 b Fo(is)h(a)h(lo)q
(cal)f(ro)q(ot.)62 2275 y(A)o(t)h(a)e(particular)h(p)q(oin)o(t)g(of)g
(execution)h(in)e(a)h(C)h(program,)d(w)o(e)i(de\014ne)h(the)g
Fg(glob)n(al)g(r)n(o)n(ot)g(set)f Fo(or)g(just)h Fg(r)n(o)n(ot)f(set)g
Fo(to)g(consist)0 2325 y(of:)51 2416 y(1.)20 b(All)13
b(v)n(alues)g(of)h Fm(static)e Fo(and)i Fm(extern)f Fo(v)n(ariables)g
(declared)i(in)e(the)i(program.)51 2499 y(2.)20 b(All)13
b(v)n(alues)g(in)h(the)g(lo)q(cal)f(ro)q(ot)h(set)h(at)f(the)g(curren)o
(t)i(execution)e(p)q(oin)o(t.)p eop
%%Page: 6 6
6 5 bop 14 8 a Fo(6)952 b Fh(The)14 b(Journal)g(of)f(C)h(Language)f(T)m
(ranslation)g({)g(REPRINT)p 0 23 1950 2 v 51 154 a Fo(3.)20
b(All)13 b(v)n(alues)g(in)h(the)g(lo)q(cal)f(ro)q(ot)h(set)h(at)f(an)o
(y)f(of)g(the)i(call)e(sites)i(in)e(the)i(call)e(c)o(hain.)51
236 y(4.)20 b(V)m(alues)e(stored)h(in)e(other)i(areas)f(of)g(memory)d
(not)j(under)h(the)g(con)o(trol)e(of)h(the)g(collector,)h(but)f
(scanned)i(b)o(y)d(the)104 286 y(collector.)h(Memory)12
b(allo)q(cated)h(b)o(y)h Fm(sbrk)e Fo(migh)o(t)g(b)q(e)i(a)f
(candidate.)1179 271 y Ff(2)1216 286 y Fo(The)g(presence)j(of)d(suc)o
(h)i(other)f(ro)q(ots)f(do)q(esn't)104 336 y(a\013ect)i(the)f(rest)h
(of)e(this)h(presen)o(tation,)h(and)e(will)g(b)q(e)h(ignored)g(for)g
(the)g(rest)h(of)e(the)i(discussion.)62 426 y(A)f(C)g(program)e(ma)o(y)
g(safely)i(use)h(a)e(conserv)n(ativ)o(e)i(garbage)e(collector)h(if)f
(it)h(satis\014es)h(the)f(follo)o(wing)e(criteria.)0
516 y Fp(\(I\))20 b Fo(Ev)o(ery)14 b(ob)r(ject)h(allo)q(cated)e
(through)g(a)h(garbage)f(collecting)g(allo)q(cator)g(that)g(ma)o(y)f
(still)h(b)q(e)h(accessed)i(is)d(accessible)i(b)o(y)104
566 y(follo)o(wing)c(c)o(hains)j(of)g(base)g(p)q(oin)o(ters)h
(originating)d(with)h(a)h(v)n(alue)f(in)h(the)g(ro)q(ot)g(set.)20
b(F)m(or)13 b(purp)q(oses)j(of)d(the)i(analysis)104 616
y(describ)q(ed)j(b)q(elo)o(w,)d(w)o(e)i(assume)e(that)h(all)f(suc)o(h)i
(base)g(p)q(oin)o(ters)f(are)h(stored)g(in)e(v)n(ariables)h(or)g
(\014elds)g(of)g(comp)q(osite)104 665 y(data)c(structures)j(declared)e
(to)f(hold)g(either)h(C)g(language)e(p)q(oin)o(ters,)i(or)f(a)g
(su\016cien)o(tly)h(large)f(in)o(tegral)f(t)o(yp)q(e)i(to)g(hold)104
715 y(a)g(p)q(oin)o(ter.)0 798 y Fp(\(I)q(I\))20 b Fo(\(This)15
b(is)f(a)g(tec)o(hnical)h(restriction)g(for)f(concurren)o(t)i(or)f
(generational)e(collectors.\))21 b(Ev)o(ery)15 b(statemen)o(t)f(that)h
(causes)104 848 y(a)k(v)n(ariable)f(to)i(hold)f(a)g(v)n(alid)f
(reference)k(to)d(an)g(ob)r(ject)i(in)o(v)o(olv)o(es)d(an)i(assignmen)o
(t)e(to)h(that)h(v)n(ariable.)34 b(This)19 b(is)104 897
y(imp)q(ossible)12 b(to)i(violate)e(in)i(a)f(program)f(that)i(strictly)
g(conforms)f(to)g([1].)k(There)e(are)f(no)g(kno)o(wn)f(cases)i(in)f
(whic)o(h)f(it)104 947 y(w)o(ould)g(otherwise)i(b)q(e)f(b)q
(ene\014cial)h(to)e(violate)g(it.)18 b(The)c(C)g(blo)q(c)o(k:)195
1030 y Fq(f)131 b Fm(char)21 b(*x;)369 1079 y Fq(f)131
b Fm(char)21 b(*y)g(=)h(malloc\(5\);)544 1129 y(if)f(\(x)h(!=)f(y\))g
(x)h(=)f(y;)544 1179 y(y)g(=)h(0;)369 1229 y Fq(g)384
1279 y Fd(:)7 b(:)g(:)195 1329 y Fq(g)104 1415 y Fo(ma)o(y)12
b(violate)g(it,)h(but)h(the)h(comparison)d(ma)o(y)g(fail)g(in)h(strict)
i(ANSI)f(C.)f(If)g Fm(malloc)g Fo(happ)q(ened)i(to)e(return)i(the)g(v)n
(alue)104 1465 y(of)c(the)h(uninitialized)f Fm(x)p Fo(,)g(then)h(the)h
(only)e(reference)j(to)d(the)i(newly)e(allo)q(cated)h(storage)g(w)o
(ould)f(b)q(e)h(through)g Fm(x)p Fo(,)f(whic)o(h)104
1515 y(had)i(nev)o(er)i(b)q(een)g(written.)62 1605 y(Clearly)j(only)g
(condition)g(\(I\))h(is)g(of)f(real)h(in)o(terest.)33
b(It)19 b(is)g(automatically)c(satis\014ed)20 b(b)o(y)e(the)h(lib)q
(eral)f(base)i(p)q(oin)o(ter)0 1655 y(de\014nition,)e(if)f(w)o(e)h
(restrict)i(ourselv)o(es)f(to)e(programs)g(that)h(strictly)g(conform)f
(to)h([1)o(].)1393 1640 y Ff(3)1441 1655 y Fo(Recall)f(that)h(in)g
(this)g(case,)h(all)0 1705 y(in)o(terior)14 b(p)q(oin)o(ters)g(are)g
(considered)i(to)d(b)q(e)i(base)f(p)q(oin)o(ters,)g(unless)h(they)g(w)o
(ere)f(deriv)o(ed)h(from)d(exterior)i(p)q(oin)o(ters.)62
1755 y(In)g(practice,)g(more)f(restrictiv)o(e)i(base)f(p)q(oin)o(ter)g
(de\014nitions)f(are)h(often)g(preferable,)g(ev)o(en)g(though)f(they)h
(imp)q(ose)f(more)0 1804 y(complicated)18 b(restrictions)i(on)f(the)g
(source)i(co)q(de.)34 b(The)20 b(lib)q(eral)e(base)h(p)q(oin)o(ter)h
(de\014nition)e(can)i(mak)o(e)d(it)i(di\016cult)f(to)0
1854 y(allo)q(cate)d(v)o(ery)h(large)f(ob)r(jects)i(without)e(making)e
(them)i(lik)o(ely)f(to)h(b)q(e)h(acciden)o(tally)f(retained.)24
b(Nearly)15 b(all)g(C)g(programs)0 1904 y(can)j(op)q(erate)h(with)f(a)g
(more)f(restrictiv)o(e)i(de\014nition.)30 b(In)19 b(most)d(resp)q
(ects,)22 b(strict)d(conformance)e(to)h(ANSI)g(C)g(is)g(m)o(uc)o(h)0
1954 y(more)c(than)g(w)o(e)h(require,)h(and)e(it)h(is)f(unclear)i(ho)o
(w)e(man)o(y)f(strictly)i(conforming)e(programs)g(there)j(are.)21
b(Hence)16 b(w)o(e)f(don't)0 2004 y(constrain)f(ourselv)o(es)h(to)f
(this)g(de\014nition.)0 2141 y Fn(Prop)r(osal)0 2232
y Fo(W)m(e)j(prop)q(ose)i(that)f(C)g(compilers)f(supp)q(ort)h(a)g
(\015ag)f Fm(-GCSAFE)g Fo(that)h(forces)h(garbage-collector-safe)e(C)h
(source)h(co)q(de)g(to)0 2281 y(b)q(e)d(compiled)e(to)i(GC-safe)f(ob)r
(ject)h(co)q(de.)24 b(In)16 b(making)d(this)j(guaran)o(tee,)g(the)g
(compiler)e(is)i(allo)o(w)o(ed)e(to)h(assume)h(that)f(all)p
0 2316 780 2 v 46 2342 a Fe(2)64 2354 y Fk(T)o(ypically)m(,)9
b(the)i(collector)e(m)o(ust)i(b)q(e)g(explicitly)e(noti\014ed)g(of)i
(suc)o(h)g(memory)m(.)46 2382 y Fe(3)64 2394 y Fk(Based)e(on)h(the)g
(most)f(natural)g(in)o(terpreta)o(tion)e(of)j(the)g(Standard,)e(w)o(e)j
(ha)o(v)o(e)e(to)h(disallo)o(w)f(writing)h(the)f(last)h(p)q(oin)o(ter)f
(to)h(an)g(ob)r(ject)f(to)h(a)g(\014le)0 2433 y(and)i(then)f(reading)g
(it)h(bac)o(k)g(in,)g(unless)g Fc(fwrite)e Fk(and)i Fc(fprintf)e
Fk(are)i(mo)q(di\014ed)f(to)h(k)o(eep)f(copies)h(of)g(all)g(suc)o(h)g
(p)q(oin)o(ters.)k(Recall)c(that)f(ANSI)j(C)0 2473 y(generally)8
b(restricts)g(p)q(oin)o(ter)g(arithmetic)f(to)j(yield)f(a)h(p)q(oin)o
(ter)e(inside)h(the)g(same)g(ob)r(ject.)k(Casts)d(to)g(and)f(from)g(in)
o(tegers)f(yield)h(implemen)o(ta)o(tio)o(n)0 2512 y(dep)q(enden)o(t)g
(results,)h(and)g(are)h(th)o(us)g(not)f(strictly)g(conforming.)p
eop
%%Page: 7 7
7 6 bop 14 8 a Fh(A)14 b(Prop)q(osal)g(for)f(GC-Safe)g(C)h(Compilation)
d(|)i(Bo)q(ehm)g(and)h(Chase)802 b Fo(7)p 0 23 1950 2
v 0 154 a(p)q(oin)o(ters)18 b(are)f(stored)i(in)e(v)n(ariables)f(or)h
(\014elds)h(of)f(comp)q(osite)f(data)h(structures)j(\(including)c
(unions\))h(declared)h(to)g(hold)0 203 y(either)d(C)f(language)f(p)q
(oin)o(ters,)h(or)f(a)h(su\016cien)o(tly)g(large)f(in)o(tegral)g(t)o
(yp)q(e)i(to)f(hold)f(a)g(p)q(oin)o(ter.)62 253 y(T)m(o)h(ensure)i
(GC-safet)o(y)e(of)g(the)h(ob)r(ject)g(co)q(de)g(the)g(compiler)e(m)o
(ust)g(ensure)j(that)f(conditions)f(\(I\))g(and)h(\(I)q(I\))f(ab)q(o)o
(v)o(e)h(are)0 303 y(main)o(tained.)216 288 y Ff(4)254
303 y Fo(It)g(should)f(further)i(attempt)e(to)h(meet)g(the)g(follo)o
(wing)e(somewhat)h(less)h(precise)i(requiremen)o(ts)e(designed)0
353 y(to)f(minim)o(ize)d(the)k(amoun)o(t)d(of)h(w)o(ork)h(and)f(degree)
j(of)d(conserv)n(ativism)g(required)h(of)g(the)g(collector:)0
444 y Fp(\(I)q(I)q(I\))21 b Fo(An)o(y)e(giv)o(en)g(p)q(oin)o(ter)g(is)g
(stored)i(in)d(con)o(tiguous)h(memory)m(.)32 b(On)19
b(a)g(mac)o(hine)f(with)h(a)g(segmen)o(ted)g(memory)e(ar-)104
494 y(c)o(hitecture,)i(the)e(segmen)o(t)f(descriptor)i(and)f(the)g
(o\013set)h(are)f(stored)g(in)g(adjacen)o(t)f(lo)q(cations.)26
b(This)17 b(requiremen)o(t)104 544 y(is)f(trivially)f(satis\014able)h
(for)h(most)e(arc)o(hitectures.)28 b(It)17 b(is)f(unfortunately)g(non)o
(trivial)f(to)i(satisfy)f(on)g(In)o(tel)h(80X86)104 594
y(mac)o(hines)c(with)g(X)h Fq(\024)g Fo(2.)0 677 y Fp(\(IV\))20
b Fo(If)13 b(feasible)g(on)g(the)g(arc)o(hitecture,)i(p)q(oin)o(ters)f
(should)f(b)q(e)h Fd(n)p Fo(-b)o(yte)f(aligned,)f(where)i
Fd(n)f Fo(is)g Fm(sizeof\(char)20 b(*\))p Fo(.)d(Other-)104
726 y(wise,)c(there)j(should)d(b)q(e)i(as)f(few)g(addresses)i(as)e(p)q
(ossible)g(at)g(whic)o(h)f(p)q(oin)o(ters)i(can)f(b)q(e)g(stored.)62
818 y(Conditions)e(\(I)q(I\)-\(IV\))i(are)f(normally)d(main)o(tained)h
(b)o(y)h(mo)q(dern)g(compilers)g(for)h(mo)q(dern)f(arc)o(hitectures,)j
(for)d(reasons)0 868 y(other)j(than)e(GC-safet)o(y)m(.)k(Condition)c
(\(I\))h(is)g(m)o(uc)o(h)f(more)g(easily)g(violated.)k(The)d(follo)o
(wing)e(discussion)i(addresses)i(\(I\).)62 917 y(W)m(e)f(prop)q(ose)g
(that)g(condition)f(\(I\))g(b)q(e)i(main)o(tained)c(for)i(all)g(p)q
(ossible)h(de\014nitions)f(of)g(base)i(p)q(oin)o(ter,)e(sub)r(ject)i
(only)e(to)0 967 y(the)j(constrain)o(t)f(that)h Fm(base)p
455 967 14 2 v 14 w(pointer)e Fo(pragmas,)g(if)g(an)o(y)m(,)h(are)g
(correct.)27 b(Assuming)15 b(a)h(lib)q(eral)f(base)i(p)q(oin)o(ter)f
(de\014nition)0 1017 y(w)o(ould)11 b(greatly)g(decrease)i(the)f
(probabilit)o(y)e(of)h(in)o(tro)q(ducing)g(a)g(problem)f(\(and)h(th)o
(us)h(mak)o(e)e Fm(-GCSAFE)g Fo(harder)i(to)f(test\),)i(but)0
1067 y(do)q(esn't)i(app)q(ear)f(to)g(signi\014can)o(tly)f(simplify)e
(the)k(compiler's)d(task)j(or)f(impro)o(v)o(e)e(the)j(qualit)o(y)d(of)i
(its)g(output.)k(Automatic)0 1117 y(transformations)11
b(that)h(in)o(tro)q(duce)h(deriv)o(ed)f(p)q(oin)o(ters)h(are)f(usually)
g(also)f(capable)h(of)g(in)o(tro)q(ducing)g(deriv)o(ed)g(p)q(oin)o
(ters)h(that)0 1166 y(p)q(oin)o(t)g(outside)i(the)f(ob)r(ject.)0
1304 y Fn(Implemen)n(tati)o(on)0 1395 y Fo(W)m(e)f(assume)g(that)h(the)
g(source)h(program)d(guaran)o(tees)i(that)g(ev)o(ery)g(accessible)h(ob)
r(ject)f(is)f(accessible)i(via)e(a)g(c)o(hain)g(of)g(base)0
1444 y(p)q(oin)o(ters.)18 b(Naiv)o(e)11 b(C)h(compilers)f(are)h(lik)o
(ely)f(to)h(preserv)o(e)h(this)f(prop)q(ert)o(y)h(in)e(the)i(ob)r(ject)
g(co)q(de,)f(as)g(will)f(most)f(sophisticated)0 1494
y(compilers)k(when)i(ask)o(ed)f(to)g(pro)q(duce)h(fully)e(debuggable)h
(ob)r(ject)h(co)q(de.)22 b(Our)16 b(goal)d(is)i(to)g(ensure)i(that)e
(this)g(prop)q(ert)o(y)h(is)0 1544 y(main)o(tained)c(at)h(minima)o(l)e
(cost)j(b)o(y)g(an)g(optimizing)d(compiler.)62 1594 y(In)16
b(order)g(to)f(mak)o(e)f(this)h(problem)f(tractable,)i(w)o(e)g(assume)f
(that)g(the)h(compiler)e(satis\014es)j(the)f(follo)o(wing)d(prop)q
(erties)0 1644 y(with)g Fm(-GCSAFE)p Fo(.)f(In)i(our)g(exp)q(erience,)h
(these)h(are)e(satis\014ed)g(b)o(y)g(most)f(existing)g(compilers,)f(ev)
o(en)j(in)e(the)i(absence)g(of)e(suc)o(h)0 1694 y(a)h(\015ag:)0
1785 y Fp(\(A\))20 b Fo(The)10 b(C)g(compiler)e(nev)o(er)j(generates)g
(co)q(de)f(to)g(recompute)g(the)g(v)n(alue)f(of)g(a)h(liv)o(e)f(base)h
(p)q(oin)o(ter)g(from)e(a)h(deriv)o(ed)h(p)q(oin)o(ter.)104
1835 y(In)k(other)g(w)o(ords,)g(all)e(liv)o(e)i(base)g(p)q(oin)o(ters)g
(are)h(explicitly)e(stored)i(at)e(run-time.)k(Most)d(compilers)f
(explicitly)g(store)104 1884 y(all)f(liv)o(e)i(v)n(alues.)360
1869 y Ff(5)0 1968 y Fp(\(B\))20 b Fo(A)o(t)14 b(ev)o(ery)g(pro)q
(cedure)i(call)c(or)i(p)q(oin)o(ter)g(dereference,)i(all)d(heap)h(lo)q
(cations)f(that)g(could)h(p)q(ossibly)f(con)o(tain)g(a)h(p)q(oin)o(ter)
104 2017 y(and)d(all)g(non-automatic)f(v)n(ariables)h(either)i(ha)o(v)o
(e)e(their)h(in)o(tended)h(v)n(alue,)e(or)h(their)g(in)o(tended)h(v)n
(alue)e(is)g(on)h(the)h(stac)o(k)104 2067 y(or)h(in)f(a)h(register.)p
0 2102 780 2 v 46 2129 a Fe(4)64 2140 y Fk(A)o(t)c(the)f(ob)r(ject)g
(co)q(de)g(lev)o(el,)g(the)g(ro)q(ot)g(set)h(should)e(b)q(e)i
(de\014ned)e(as)i(the)f(v)n(alues)g(scanned)f(b)o(y)h(the)h(garbage)e
(collector)g(to)h(b)q(egin)g(its)h(tra)o(v)o(ersal.)0
2180 y(This)i(normally)d(includes)g(all)i(v)n(alues)f(stored)g(in)h
(the)g(stac)o(k,)f(the)h(registers,)f(and)g(v)n(arious)g(statically)f
(allo)q(cated)g(data)h(segmen)o(ts.)46 2208 y Fe(5)64
2219 y Fk(There)j(are)f(sometimes)f(reasons)h(not)h(to)g(do)g(so)h([7)o
(].)22 b(An)14 b(optimizer)d(could)h(violate)f(this)i(prop)q(ert)o(y)e
(as)j(follo)o(ws.)21 b(Assume)12 b(a)i(restrictiv)o(e)0
2259 y(base)d(p)q(oin)o(ter)g(de\014nition.)j(Consider)d(a)i(lo)q(op)e
(that)g(sums)g(the)h(en)o(tries)f(of)h(the)f(heap)g(allo)q(cated)f
(arra)o(y)h Fc(a)h Fk(in)g(order,)f(and)g(that)g Fc(a)h
Fk(is)h(liv)o(e)e(at)h(the)0 2298 y(end)d(of)i(the)e(lo)q(op.)14
b(On)d(man)o(y)d(mac)o(hines,)g(the)i(compiler)e(is)i(lik)o(ely)f(to)h
(p)q(erform)e(induction)g(v)n(ariable)g(elimination,)f(and)j(instead)e
(step)i(a)g(p)q(oin)o(ter)0 2338 y(through)e(the)i(arra)o(y)m(.)j(If)d
(there)f(is)h(a)h(lot)e(of)h(register)f(pressure,)f(and)i(the)f(arra)o
(y)g(has)h(kno)o(wn)f(size,)h(it)g(ma)o(y)f(fail)h(to)g(store)f(the)g
(p)q(oin)o(ter)g(to)h(the)f(base)0 2377 y(of)i(the)g(arra)o(y)m(,)f
(and)g(instead)g(recompute)e(it)j(b)o(y)g(subtracting)d(the)j(size)g
(of)g(the)f(arra)o(y)g(from)g(the)h(\014nal)f(v)n(alue)g(of)h(the)g(p)q
(oin)o(ter)e(that)i(w)o(as)g(stepp)q(ed)0 2417 y(through)e(the)i(arra)o
(y)m(.)p eop
%%Page: 8 8
8 7 bop 14 8 a Fo(8)952 b Fh(The)14 b(Journal)g(of)f(C)h(Language)f(T)m
(ranslation)g({)g(REPRINT)p 0 23 1950 2 v 62 154 a Fo(It)f(follo)o(ws)e
(from)g(prop)q(ert)o(y)j(\(A\))f(that)g(ob)r(jects)h(that)f(are)g
(accessible)h(via)e(base)i(p)q(oin)o(ters)f(visible)f(to)h(the)g
(collector)g(ha)o(v)o(e)0 203 y(alw)o(a)o(ys)k(b)q(een)j(accessible)g
(via)d(base)i(p)q(oin)o(ters.)30 b(\(Assume)17 b(that)g
Fd(x)h Fo(w)o(as)f(not)g(accessible)i(via)e(base)h(p)q(oin)o(ters,)g
(and)f(then)0 253 y(b)q(ecomes)f(accessible)h(via)e(base)h(p)q(oin)o
(ters.)24 b(This)15 b(is)h(imp)q(ossible)e(at)h(the)i(source)g(lev)o
(el,)e(since)h(p)q(oin)o(ters)h(computed)e(from)0 303
y(deriv)o(ed)g(p)q(oin)o(ters)f(are)h(nev)o(er)g(considered)h(to)e(b)q
(e)g(base)h(p)q(oin)o(ters.)20 b(Prop)q(ert)o(y)15 b(\(A\))f(ensures)i
(that)f(the)f(compiler)f(do)q(es)i(not)0 353 y(in)o(tro)q(duce)g(a)e
(violation)f(of)h(this)h(rule.\))62 403 y(Hence)g(prop)q(ert)o(y)g
(\(B\))f(could)g(fail)e(to)i(hold)f(only)g(if)g(the)h(lo)q(cation)f(or)
h(v)n(ariable)e(w)o(ere)j(dead.)k(It)13 b(is)f(extremely)g(rare)i(that)
0 452 y(a)g(C)f(compiler)g(can)h(safely)g(determine)f(this)h(for)g(an)o
(ything)f(other)h(than)g(an)g(automatic)e(v)n(ariable.)62
502 y(Note)j(that)f(the)h(lifetime)e(of)g(a)i(deriv)o(ed)f(p)q(oin)o
(ter)h(ends)g(at)f(an)h(instruction)f(that)h(dereferences)i(it.)j(The)
14 b(p)q(oin)o(ter)h(ma)o(y)0 552 y(b)q(e)g(compared)f(or)h(otherwise)g
(manipulated)e(afterw)o(ards,)i(but)f(for)h(purp)q(oses)h(of)e
(GC-safet)o(y)g(there)i(is)e(no)g(longer)h(a)f(need)0
602 y(to)e(consider)h(it)f(a)g(p)q(oin)o(ter.)17 b(Th)o(us,)c(under)g
(assumption)e(\(A\),)h(the)h(real)f(requiremen)o(t)g(for)g(the)g
(compiler)f(is)h(that)h(whenev)o(er)0 652 y(a)j(deriv)o(ed)i(p)q(oin)o
(ter)f(to)f Fd(x)h Fo(is)f(dereferenced,)k Fd(x)d Fo(m)o(ust)e(b)q(e)j
(accessible)g(via)e(base)h(p)q(oin)o(ters.)27 b(This)17
b(can)g(b)q(e)g(ensured)i(if)d(w)o(e)0 702 y(guaran)o(tee)e(that:)0
793 y Fp(\(I'\))20 b Fo(A)o(t)13 b(ev)o(ery)g(dereference)i(of)d(a)g(p)
q(ossibly)g(deriv)o(ed)h(p)q(oin)o(ter)g Fd(x)p Fo(,)f(a)g(base)h(p)q
(oin)o(ter)f(\(p)q(ossibly)g(indirectly\))h(p)q(oin)o(ting)e(to)h(the)
104 843 y(same)h(ob)r(ject)h(as)g Fd(x)g Fo(is)g(liv)o(e)f(and)h
(visible)f(to)h(the)g(collector.)62 934 y(Requiremen)o(t)f(\(I'\))h
(can)g(b)q(e)h(satis\014ed)f(b)o(y)g(ensuring)g(the)h(follo)o(wing:)0
1025 y Fp(\(Ia\))20 b Fo(All)13 b(lo)q(cal)g(ro)q(ots)i(ha)o(v)o(e)f
(their)g(v)n(alue)f(visible)g(to)h(the)h(collector)f(\(i.e.,)f(are)h
(stored)h(in)f(a)f(register)i(or)f(on)g(the)h(stac)o(k\))f(at)104
1075 y(ev)o(ery)g(pro)q(cedure)g(call.)j(\(V)m(ariables)c(that)g(are)g
(kno)o(wn)g(to)g(p)q(oin)o(t)f(to)h(an)g(otherwise)g(accessible)i(ob)r
(ject)f(do)e(not)h(ha)o(v)o(e)104 1125 y(to)h(b)q(e)h(made)e(a)o(v)n
(ailable.)18 b(It)c(is)g(not)h(necessary)h(to)e(meet)g(this)h
(requiremen)o(t)f(if)g(the)h(called)f(function)g(is)g(kno)o(wn)g(not)
104 1175 y(to)g(dereference)i(deriv)o(ed)f(p)q(oin)o(ters.\))0
1258 y Fp(\(Ib\))20 b Fo(A)o(t)12 b(ev)o(ery)i(dereference)i(of)c
Fd(x)p Fo(,)g(either)h(a)g(kno)o(wn)f(base)h(p)q(oin)o(ter)g(for)g
Fd(x)f Fo(is)h(visible)f(to)g(the)i(collector,)f(or)f(all)g(lo)q(cal)g
(ro)q(ots)104 1308 y(are)j(visible.)21 b(\(If)15 b Fd(x)f
Fo(is)h(kno)o(wn)g(to)g(b)q(e)g(deriv)o(ed)h(from)d(either)j
Fd(y)h Fo(or)e Fd(z)r Fo(,)g(then)g(it)g(su\016ces)h(to)f(k)o(eep)h(b)q
(oth)f Fd(y)i Fo(and)e Fd(z)i Fo(liv)o(e)104 1357 y(at)d(the)g
(dereference.\))62 1449 y(Both)19 b(\(Ia\))g(and)f(\(Ib\))h(require)h
(that)f(a)f(few)h(otherwise)g(dead)g(v)n(ariables)f(ma)o(y)f(ha)o(v)o
(e)i(to)f(b)q(e)h(either)h(main)o(tained)c(in)0 1499
y(registers)j(or)f(spilled)f(on)o(to)g(the)i(stac)o(k.)30
b(W)m(e)17 b(exp)q(ect)i(that)f(they)g(will)f(t)o(ypically)f(require)j
(that)e(v)o(ery)i(few)e(v)n(ariables)g(b)q(e)0 1548 y(k)o(ept)d(liv)o
(e.)k(User)d(in)o(tro)q(duced)g(v)n(ariables)e(that)h(are)g(dead)g(at)g
(call-sites)g(or)g(dereference)j(sites)e(are)f(probably)f(not)h(all)f
(that)0 1598 y(frequen)o(t)20 b(to)f(start)g(with.)33
b(Man)o(y)18 b(of)h(them)f(can)h(b)q(e)h(determined)f(not)f(to)h(con)o
(tain)g(heap)g(p)q(oin)o(ters.)34 b(Others)20 b(can)f(b)q(e)0
1648 y(determined)c(to)g(p)q(oin)o(t)g(to)g(the)g(same)g(ob)r(ject)h
(as)f(a)g(parameter,)f(in)h(whic)o(h)g(case)h(the)g(caller)f(will)f
(already)g(ha)o(v)o(e)h(satis\014ed)0 1698 y(the)e(requiremen)o(t.)18
b(Stores)c(in)o(tro)q(duced)g(b)o(y)e(\(Ia\))h(and)g(\(Ib\))g(can)g
(usually)f(b)q(e)i(mo)o(v)o(ed)d(out)i(of)f(lo)q(ops,)g(further)i
(reducing)f(the)0 1748 y(cost.)62 1797 y(The)21 b(added)g(cost)g(is)f
(lik)o(ely)f(to)h(b)q(e)h(essen)o(tially)f(zero)i(on)e(register)h
(windo)o(w)f(arc)o(hitectures)i(with)e(large)g(windo)o(ws)0
1847 y(\(notably)13 b(SP)m(AR)o(C\))g(where)h(there)h(is)e(t)o
(ypically)f(an)i(ample)d(supply)j(of)f(registers)i(for)e(p)q(oin)o
(ter-in)o(tensiv)o(e)g(co)q(de,)h(and)g(there)0 1897
y(is)e(no)h(incremen)o(tal)e(cost)j(for)e(sa)o(ving)g(these)i
(registers)g(across)f(pro)q(cedure)i(calls.)i(It)12 b(is)h(lik)o(ely)e
(to)h(b)q(e)i(more)d(noticeable,)i(but)0 1947 y(still)g(minor,)f(for)h
(arc)o(hitectures)j(with)e(few)o(er)g(registers,)h(suc)o(h)g(as)f(the)g
(In)o(tel)g(80X86)f(pro)q(cessors.)0 2084 y Fn(Source-Lev)n(el)22
b(Implemen)n(tati)o(on)0 2175 y Fo(Under)14 b(most)f(circumstances,)h
(an)f(existing)g(compiler)f(will)g(already)h(satisfy)g(all)g
(requiremen)o(ts)g(except)i(\(I'\).)e(W)m(e)g(further)0
2225 y(assume)k(that)g(an)g(existing)g(compiler)e(will)h(not)h
(generate)i(co)q(de)f(that)f(in)o(tro)q(duces)h(p)q(oin)o(ter)f
(dereferences)k(that)c(do)g(not)0 2275 y(corresp)q(ond)d(to)d(an)o(y)h
(source)h(expression.)19 b(Ideally)11 b(w)o(e)h(w)o(ould)g(lik)o(e)f
(to)h(ensure)h(that)f(all)f(compiler)g(bac)o(k-ends)i(b)q(e)f(mo)q
(di\014ed)0 2325 y(to)k(guaran)o(tee)g(\(I'\).)f(This)g(is)h(probably)f
(not)h(practical)f(in)h(all)e(cases.)25 b(Here)17 b(w)o(e)f(presen)o(t)
h(a)f(strategy)g(for)f(implemen)o(ting)0 2374 y(this)d(prop)q(osal)g
(that)h(requires)g(at)g(most)e(minim)o(al)e(mo)q(di\014cations)h(to)i
(compiler)f(bac)o(k-ends,)i(at)f(the)h(exp)q(ense)h(of)e(requiring)0
2424 y(an)19 b(additional)f(source-to-source)k(translation)d(pass.)36
b(This)20 b(clearly)g(in)o(v)o(olv)o(es)e(a)i(cost)g(in)f(compilation)e
(sp)q(eed)k(when)0 2474 y(GC-safet)o(y)13 b(is)h(needed.)20
b(On)14 b(the)g(other)h(hand,)e(nearly)h(all)f(of)g(the)h(w)o(ork)g
(needs)h(to)f(b)q(e)g(done)h(only)e(once.)p eop
%%Page: 9 9
9 8 bop 14 8 a Fh(A)14 b(Prop)q(osal)g(for)f(GC-Safe)g(C)h(Compilation)
d(|)i(Bo)q(ehm)g(and)h(Chase)802 b Fo(9)p 0 23 1950 2
v 62 154 a(A)17 b(more)f(direct)i(implem)o(en)o(tation)c(in)i(the)i(C)e
(compiler)g(itself)g(could)h(use)h(a)e(v)o(ery)h(similar)e(approac)o
(h.)26 b(A)17 b(compiler)0 203 y(that)d(generates)h(C)f(as)g(its)g(in)o
(termediate)f(language)g(could)h(incorp)q(orate)g(a)g(greatly)g
(simpli\014ed)e(v)o(ersion)i(of)f(the)h(prepass.)62 253
y(Instead)h(of)e(guaran)o(teeing)h(\(I'\),)f(the)i(C)e(compiler)g
(itself)g(m)o(ust)g(pro)o(vide)h(the)g(follo)o(wing:)0
345 y Fp(\(C\))20 b Fo(W)m(e)f(m)o(ust)g(b)q(e)h(able)f(to)g(de\014ne)i
(a)e(macro)f Fm(KEEP)p 876 345 14 2 v 15 w(LIVE)p Fo(\()p
Fd(e;)7 b(y)q(;)g(t;)g(tmp)p Fo(\))18 b(whose)i(v)n(alue)f(is)g(the)h
(v)n(alue)f(of)g Fd(e)p Fo(,)h(but)g(that)104 394 y(guaran)o(tees)d
(that)g(the)h(p)q(oin)o(ter)f(or)f(in)o(teger)h(v)n(ariable)f
Fd(y)j Fo(is)d(accessible)i(to)f(the)g(collector)g(un)o(til)f(an)o(y)h
(dereferences)104 444 y(within)c Fd(e)h Fo(are)h(completely)e(ev)n
(aluated.)18 b(The)c(parameter)g Fd(t)g Fo(will)e(alw)o(a)o(ys)h(b)q(e)
i(the)g(t)o(yp)q(e)f(of)f Fd(e)p Fo(,)h(and)g Fd(tmp)g
Fo(will)f(alw)o(a)o(ys)104 494 y(b)q(e)18 b(a)f(lo)q(cal)g(register)h
(v)n(ariable)f(of)f(t)o(yp)q(e)i Fd(t)g Fo(that)f(is)g(not)h(otherwise)
g(in)f(use)i(during)e(the)h(macro)e(in)o(v)o(o)q(cation.)27
b(W)m(e)104 544 y(assume)14 b(there)j(is)d(a)h(sp)q(ecial)g(v)o(ersion)
g(of)g(this)g(macro)e Fm(KEEP)p 1059 544 V 15 w(LIVE)p
1162 544 V 15 w(VOID)p Fo(\()p Fd(e;)21 b(y)q Fo(\))16
b(for)f(the)g(case)h(in)f(whic)o(h)g Fd(t)f Fo(is)h Fm(void)p
Fo(.)104 594 y(Both)j Fd(t)f Fo(and)h Fd(tmp)f Fo(will)f(b)q(e)j
(omitted)d(in)h(some)g(of)g(the)h(follo)o(wing)d(discussion.)29
b(Ev)n(aluation)16 b(of)h Fm(KEEP)p 1759 594 V 15 w(LIVE)p
Fo(\()p Fd(e;)7 b(y)q Fo(\))104 643 y(should)13 b(not)h(b)q(e)h
(appreciably)e(more)g(exp)q(ensiv)o(e)i(than)f(ev)n(aluating)f
Fd(e)p Fo(.)104 710 y(The)i(precise)i(de\014nition)d(of)h
Fm(KEEP)p 653 710 V 14 w(LIVE)f Fo(will)g(probably)g(b)q(e)i(compiler)d
(dep)q(enden)o(t.)23 b(The)16 b(follo)o(wing)c(de\014nition)j(of)104
760 y Fm(KEEP)p 195 760 V 15 w(LIVE)p Fo(\()p Fd(e;)7
b(y)q(;)g(t;)g(tmp)p Fo(\))13 b(is)h(lik)o(ely)e(to)i(su\016ce)h(for)e
(most)g(compilers:)195 851 y Fm(\()22 b Fd(tmp)g Fm(=)f(\()p
Fd(e)p Fm(\),)p 486 851 V 38 w(SINK)g(=)g(\(void)g(*\))p
Fd(y)q Fm(,)h Fd(tmp)g Fm(\))104 942 y Fo(where)p 225
942 V 30 w Fm(SINK)12 b Fo(is)g(an)h Fm(extern)21 b(void)g
Fq(\003)g Fm(volatile)11 b Fo(v)n(ariable.)17 b(This)c(mak)o(es)f(it)g
(extremely)h(di\016cult)f(for)h(a)f(compiler)104 992
y(to)f(p)q(erm)o(ute)h(the)h(assignmen)o(t)d(to)p 647
992 V 28 w Fm(SINK)h Fo(with)g(dereferences)k(in)d Fd(e)g
Fo(and)f(still)g(b)q(e)i(standard)f(conforming.)j(The)d(extra)104
1042 y(assignmen)o(t)h(to)h Fd(tmp)h Fo(can)f(easily)g(b)q(e)h
(optimized)e(out)h(on)g(a)g(register-based)i(mac)o(hine)d(arc)o
(hitecture.)21 b(Eliminating)104 1092 y(the)14 b(assignmen)o(t)f(to)p
442 1092 V 29 w Fm(SINK)g Fo(requires)i(either)g(a)e(p)q(ostpass)i(o)o
(v)o(er)f(the)g(assem)o(bly)f(co)q(de,)h(or)f(a)h(corresp)q(onding)h
(facilit)o(y)104 1142 y(built)i(in)o(to)h(the)h(compiler)e(bac)o
(k-end.)718 1126 y Ff(6)769 1142 y Fo(In)h(addition)f(to)h(the)h
(increased)h(register)g(pressure)g(men)o(tioned)e(ab)q(o)o(v)o(e,)104
1191 y(this)13 b(implem)o(en)o(tation)d(of)i Fm(KEEP)p
616 1191 V 15 w(LIVE)g Fo(ma)o(y)e(inhibit)i(instruction)h(sc)o
(heduling)g(b)o(y)f(adding)g(spurious)h(dep)q(endencies)104
1241 y(b)q(et)o(w)o(een)f(memory)d(reference)k(instructions.)18
b(Some)10 b(sc)o(heduling)h(can)g(b)q(e)h(p)q(erformed)e(after)i(remo)o
(ving)d(assignmen)o(ts)104 1291 y(to)p 157 1291 V 29
w Fm(SINK)p Fo(,)k(but)h(careless)h(sc)o(heduling)f(is)g(unsafe.)104
1357 y(This)j(de\014nition)f(of)g Fm(KEEP)p 530 1357
V 15 w(LIVE)g Fo(assumes)h(that)g Fd(e)g Fo(ma)o(y)e(terminate.)27
b(T)m(o)16 b(v)o(erify)g(this,)h(consider)h(the)g(expression)104
1407 y Fm(KEEP)p 195 1407 V 15 w(LIVE\(f\(\),)i(y\))p
Fo(,)f(where)h(f)f(con)o(tains)g(dereferences)k(inside)c(an)g(easily)g
(recognizable)g(in\014nite)g(lo)q(op.)34 b(The)104 1457
y(compiler)13 b(w)o(ould)g(b)q(e)i(fully)d(justi\014ed)j(in)f
(optimizing)d(out)j(the)h(assignmen)o(t)e(to)p 1372 1457
V 30 w Fm(SINK)p Fo(,)f(since)j(it)f(is)g(pro)o(v)n(ably)f(nev)o(er)104
1507 y(executed.)33 b(In)18 b(practice,)i(this)e(ma)o(y)e(happ)q(en)j
(if)f(the)g(call)g(to)g Fm(f)g Fo(is)g(in-lined.)30 b(It)18
b(is)g(hard)h(to)f(de\014ne)h Fm(KEEP)p 1851 1507 V 15
w(LIVE)104 1557 y Fo(without)14 b(suc)o(h)i(an)e(assumption.)19
b(T)m(o)14 b(mak)o(e)g(it)g(p)q(ossible)h(for)f(the)i(prepass)g(to)e
(ensure)j(that)d(all)g(function)g(calls)h(are)104 1606
y(view)o(ed)f(b)o(y)f(the)i(compiler)d(as)i(p)q(ossibly)g(terminating,)
e(w)o(e)i(need)h(the)f(follo)o(wing:)0 1689 y Fp(\(D\))19
b Fo(W)m(e)14 b(m)o(ust)e(b)q(e)j(able)e(to)g(de\014ne)i(a)f(macro)e
Fm(DISGUISED)p 942 1689 V 14 w(ZERO)h Fo(that)g(alw)o(a)o(ys)g(returns)
i(the)f(constan)o(t)g(0,)f(but)h(is)g(treated)104 1739
y(b)o(y)20 b(compiler)e(optimizations)g(as)j(returning)f(an)g(unkno)o
(wn)g(v)n(alue.)36 b(The)21 b(one)f(exception)h(should)f(b)q(e)h(that)f
(all)104 1789 y(instructions)c(that)f(will)e(nev)o(er)j(b)q(e)g
(executed)h(as)e(a)g(result)g(of)g Fm(DISGUISED)p 1299
1789 V 14 w(ZERO)p Fo('s)f(v)n(alue,)g(and)h(all)f(branc)o(hes)i(that)
104 1839 y(are)e(nev)o(er)i(tak)o(en,)e(should)g(b)q(e)h(eliminated.)i
(This)d(could)g(b)q(e)h(implemen)o(ted)d(b)o(y)i(de\014ning)g
Fm(DISGUISED)p 1744 1839 V 14 w(ZERO)f Fo(to)h(b)q(e)p
104 1889 V 117 1889 a Fm(zero)e Fo(where)p 338 1889 V
30 w Fm(zero)g Fo(is)g(an)h(external)g(v)o(olatile)f(v)n(ariable)f
(initialized)h(to)g(0.)18 b(A)13 b(simple)e(p)q(ostpass)j(o)o(v)o(er)f
(the)g(compiler)104 1939 y(output)h(could)g(again)e(eliminate)g(the)j
(resulting)f(dead)g(co)q(de.)62 2030 y(Our)h(prepass)g(then)f
(transforms)g(the)g(co)q(de)h(in)e(the)i(follo)o(wing)c(w)o(a)o(ys:)51
2121 y(1.)20 b(All)9 b(imm)o(ediate)f(sub)q(expressions)k
Fd(e)e Fo(of)f(function)h(calls)f(and)h(dereferences)j(whose)d(result)h
(ma)o(y)d(con)o(tain)h(an)h(otherwise)104 2171 y(inaccessible)18
b(base)h(p)q(oin)o(ter)f(are)g(replaced)g(b)o(y)g(\()p
Fd(tmp)g Fo(=)g(\()p Fd(e)p Fo(\)\),)h(where)g Fd(tmp)f
Fo(is)f(a)h(newly)f(in)o(tro)q(duced)i(temp)q(orary)104
2221 y(register)14 b(v)n(alue)f(of)g(the)h(righ)o(t)f(t)o(yp)q(e.)18
b(F)m(or)13 b(our)h(purp)q(oses,)g(a)f(dereference)k(is)c(an)g
(expression)i(that)e(uses)i Fm(*)p Fo(,)d Fm(->)p Fo(,)h(or)g
Fm([])104 2271 y Fo(as)h(its)g(outer)g(op)q(erand.)51
2354 y(2.)20 b(All)15 b(functions)h(that)g(ma)o(y)e(directly)i(or)g
(indirectly)g(reference)i(deriv)o(ed)f(p)q(oin)o(ters)f(and)g(cannot)g
(b)q(e)h(guaran)o(teed)f(to)104 2403 y(alw)o(a)o(ys)d(return)i(are)f
(augmen)o(ted)f(with)h(the)g(initial)e(statemen)o(t)p
0 2438 780 2 v 46 2465 a Fe(6)64 2477 y Fk(Use)f(of)g(a)h(reserv)o(ed)d
(iden)o(ti\014er)g(suc)o(h)i(as)p 611 2477 11 2 v 24
w Fc(SINK)f Fk(ensures)g(that)h(con\015icts)e(with)i(other)g(iden)o
(ti\014ers)e(are)h(unlik)o(ely)m(.)p eop
%%Page: 10 10
10 9 bop 14 8 a Fo(10)931 b Fh(The)14 b(Journal)g(of)f(C)h(Language)f
(T)m(ranslation)g({)g(REPRINT)p 0 23 1950 2 v 195 154
a Fm(if)21 b(\(DISGUISED)p 483 154 14 2 v 14 w(ZERO\))g
Fq(f)g Fg(build)15 b(C)g Fm(;)21 b(return)g Fg(C)14 b
Fm(;)22 b Fq(g)104 244 y Fo(where)13 b(C)f(is)h(some)e(expression)i(of)
f(the)h(correct)h(t)o(yp)q(e.)k(This)12 b(ensures)i(that)f(the)g
(compiler)d(ma)o(y)h(not)h(eliminate)e(co)q(de)104 294
y(imm)o(ediately)h(follo)o(wing)g(a)j(function)g(call.)51
376 y(3.)20 b(Whenev)o(er)13 b(requiremen)o(t)g(\(Ia\))f(implies)f
(that)h(v)n(ariables)g Fd(x)1030 382 y Ff(1)1048 376
y Fo(,)g Fd(x)1096 382 y Ff(2)1115 376 y Fo(,)g Fd(:)7
b(:)g(:)e Fo(,)12 b Fd(x)1242 382 y Fb(n)1277 376 y Fo(m)o(ust)f(b)q(e)
i(liv)o(e)f(at)g(a)g(call)g(to)g Fd(f)t Fo(,)h(w)o(e)g(replace)104
426 y(the)h(call)f(b)o(y:)195 516 y Fm(KEEP)p 286 516
V 15 w(LIVE\()p Fd(:)7 b(:)g(:)t Fm(KEEP)p 553 516 V
15 w(LIVE\()21 b(KEEP)p 787 516 V 15 w(LIVE\()p Fd(f)c
Fm(\()p Fd(:)7 b(:)g(:)e Fm(\),)14 b Fd(x)1105 522 y
Ff(1)1137 516 y Fm(\),)g Fd(x)1219 522 y Ff(2)1251 516
y Fm(\),)p Fd(:)7 b(:)g(:)e Fm(,)13 b Fd(x)1409 522 y
Fb(n)1445 516 y Fm(\))104 606 y Fo(If)e(the)g(t)o(yp)q(e)h(of)e
Fd(e)i Fo(is)f Fm(void)p Fo(,)f(w)o(e)h(use)h Fm(KEEP)p
744 606 V 15 w(LIVE)p 847 606 V 15 w(VOID)e Fo(instead.)18
b(Note)11 b(that)g(step)h(1)f(guaran)o(tees)h(that)f(all)f(lo)q(cal)h
(ro)q(ots)104 656 y(are)j(either)h(in)e(lo)q(cal)g(v)n(ariables)g(or,)h
(in)f(v)o(ery)h(un)o(usual)g(cases,)h(in)e(\014elds)i(of)e(lo)q(cal)g
(union)g(or)h(structure)i(v)n(ariables.)51 738 y(4.)k(Whenev)o(er)13
b(requiremen)o(t)g(\(Ib\))g(implies)d(that)j(v)n(ariables)f
Fd(x)1033 744 y Ff(1)1051 738 y Fo(,)g Fd(x)1099 744
y Ff(2)1130 738 y Fo(,)h Fd(:)7 b(:)g(:)e Fo(,)12 b Fd(x)1258
744 y Fb(n)1293 738 y Fo(m)o(ust)g(b)q(e)h(liv)o(e)e(at)i(a)f
(dereference)k(expres-)104 788 y(sion)d Fd(e)p Fo(,)h(w)o(e)g(replace)h
Fd(e)f Fo(b)o(y:)195 878 y Fm(KEEP)p 286 878 V 15 w(LIVE\()p
Fd(:)7 b(:)g(:)t Fm(KEEP)p 553 878 V 15 w(LIVE\()21 b(KEEP)p
787 878 V 15 w(LIVE\()13 b Fd(e)p Fo(,)g Fd(x)990 884
y Ff(1)1022 878 y Fm(\),)h Fd(x)1104 884 y Ff(2)1136
878 y Fm(\),)p Fd(:)7 b(:)g(:)e Fm(,)14 b Fd(x)1295 884
y Fb(n)1331 878 y Fm(\))51 968 y Fo(5.)20 b(W)m(e)13
b(add)h(declarations)g(for)f(the)i(lo)q(cal)e(v)n(ariables)g(required)i
(b)o(y)f(an)o(y)f(of)g(the)i(ab)q(o)o(v)o(e)e(steps.)62
1057 y(F)m(urther)h(optimizations)c(are)j(p)q(ossible.)18
b(F)m(or)12 b(example,)f(nested)j Fm(KEEP)p 1174 1057
V 15 w(LIVE)p Fo(s)e(for)g(the)i(same)d(v)n(ariable)h(can)h(usually)e
(b)q(e)0 1107 y(coalesced.)62 1157 y(Our)k(\014rst)f(example)f(migh)o
(t)f(b)q(e)i(annotated)g(as:)104 1246 y Fm(int)21 b(f\(\))104
1296 y Fq(f)191 1346 y Fm(int)g(*a,)g(*b;)191 1395 y(int)g(i,)h(sum;)
191 1445 y(register)e(int)h(*)h(tmp1;)191 1495 y(register)e(int)h
(tmp2;)191 1595 y(if)g(\(DISGUISED_ZERO\))e(return\(0\);)191
1644 y(a)j(=)f(\(int)g(*\)malloc\(100000)e(*)i(sizeof)g(\(int\)\);)191
1694 y(b)h(=)f(KEEP_LIVE\()f(\(int)h(*\)malloc\(100000)e(*)i(sizeof)g
(\(int\)\),)278 1744 y(a,)h(int)f(*,)g(tmp1\);)191 1794
y(...)191 1844 y(for)g(\(i)h(=)f(0;)g(i)h(<)g(100000;)e(i++\))h
Fq(f)278 1894 y Fm(sum)g(+=)h(KEEP_LIVE\(a[i],)c(a,)k(int,)f(tmp2\))f
(+)431 1943 y(KEEP_LIVE\(b[i],)e(b,)k(int,)f(tmp2\);)191
1993 y Fq(g)191 2043 y Fm(return\(sum\);)104 2093 y Fq(g)62
2163 y Fo(This)15 b(assumes)g(that)g Fm(malloc)e Fo(app)q(eared)j(in)f
(a)f Fm(base)p 911 2163 V 15 w(pointer)f Fo(pragma.)20
b(It)15 b(otherwise)g(assumes)g(that)g(the)h(prepass)0
2213 y(is)e(not)h(particularly)f(clev)o(er.)20 b(The)15
b(output)g(w)o(ould)f(b)q(e)h(simpler)e(if)h(it)g(could)g(determine)h
(that)f(the)i(b)q(o)q(dy)e(of)g(the)h(function)0 2263
y(alw)o(a)o(ys)9 b(terminates,)g(or)h(that)g Fm(malloc)e
Fo(do)q(es)i(not)g(dereference)i(deriv)o(ed)f(p)q(oin)o(ters,)f(or)g
(that)f(the)i(second)f Fm(KEEP)p 1714 2263 V 15 w(LIVE)f
Fo(implies)0 2313 y(the)k(\014rst.)19 b(\(Note)13 b(that)g(there)h(are)
f(p)q(ossible)h(de\014nitions)e(of)h Fm(malloc)e Fo(suc)o(h)j(that)e
(the)i(\014rst)f Fm(KEEP)p 1521 2313 V 15 w(LIVE)f Fo(is)h(necessary)m
(.)19 b(Also)0 2363 y(the)14 b(other)h(statemen)o(ts)f(w)o(ould)f(b)q
(e)i(falsi\014ed)e(if)g(the)i(co)q(de)f(in)g(the)g(ellipsis)f(pro)o(v)n
(ably)g(failed)g(to)h(terminate.\))62 2412 y(Although)e(w)o(e)g(ha)o(v)
o(e)g(added)g(a)f(signi\014can)o(t)h(amoun)o(t)e(of)h(clutter)i(to)f(a)
g(v)o(ersion)g(of)f(the)h(program)f(that)h(the)g(programmer)0
2462 y(will)d(hop)q(efully)h(nev)o(er)h(see,)h(none)f(of)f(this)h(w)o
(ould)e(normally)f(add)j(an)o(y)f(run)o(time)f(o)o(v)o(erhead.)17
b(The)11 b(conditional)e(return)j(could)0 2512 y(b)q(e)i(easily)f
(eliminated.)j(The)e Fm(KEEP)p 565 2512 V 15 w(LIVE)f
Fo(calls)g(force)h(the)h(v)n(ariables)e Fm(a)g Fo(and)g
Fm(b)h Fo(to)f(b)q(e)h(k)o(ept)g(in)g(registers)h(throughout)e(the)p
eop
%%Page: 11 11
11 10 bop 14 8 a Fh(A)14 b(Prop)q(osal)g(for)f(GC-Safe)g(C)h
(Compilation)d(|)i(Bo)q(ehm)g(and)h(Chase)781 b Fo(11)p
0 23 1950 2 v 0 154 a(lo)q(op.)16 b(Since)d(they)f(w)o(ould)e(need)j
(to)e(b)q(e)h(there)h(at)f(some)e(p)q(oin)o(t)h(an)o(yw)o(a)o(y)m(,)f
(this)i(adds)g(instructions)g(only)f(if)f(to)q(o)i(few)f(registers)0
203 y(are)16 b(a)o(v)n(ailable.)j(The)d(optimization)c(w)o(e)k
(discussed)h(at)e(the)h(b)q(eginning)e(could)h(still)f(b)q(e)i(p)q
(erformed,)f(if)f(it)h(w)o(ere)h(found)f(to)0 253 y(b)q(e)g(desirable.)
0 390 y Fn(Summary)0 481 y Fo(Ideally)9 b(C)g(compilers)f(w)o(ould)h
(pro)o(vide)g(a)g Fm(-GCSAFE)f Fo(\015ag)h(that)g(ensures)i(that)f
(only)e(garbage)h(collector)h(safe)f(transformations)0
531 y(are)i(p)q(erformed)e(on)h(the)h(co)q(de.)18 b(Ho)o(w)o(ev)o(er,)
10 b(this)h(is)f(not)g(alw)o(a)o(ys)f(practical.)16 b(Here)c(w)o(e)e
(rep)q(eat)h(the)g(minim)n(um)6 b(set)11 b(of)e(essen)o(tial)0
581 y(and)h(in)o(teresting)h(requiremen)o(ts)g(on)f(a)h(C)f(compiler)f
(suc)o(h)i(that)g(GC)f(safet)o(y)h(can)f(b)q(e)h(guaran)o(teed)g(b)o(y)
g(an)f(additional)f(prepass)0 631 y(o)o(v)o(er)i(the)h(source)g(co)q
(de.)18 b(W)m(e)11 b(consider)h(a)e(requiremen)o(t)h(to)g(b)q(e)h(in)o
(teresting)g(if)e(w)o(e)h(are)h(a)o(w)o(are)e(of)h(a)g(violation)e(b)o
(y)h(an)h(existing)0 681 y(compiler,)i(or)h(w)o(e)h(feel)g(it)f(could)g
(b)q(e)h(violated)f(in)g(the)h(in)o(terest)h(of)e(a)g(legitimate)f
(optimization.)k(W)m(e)d(w)o(ould)g(exp)q(ect)i(that)0
730 y(most)j(compilers)g(could)h(meet)f(these)j(requiremen)o(ts)e(for)g
(all)f(compilations,)f(and)i(in)g(fact,)h(that)f(man)o(y)e(already)i
(do.)0 780 y(Ho)o(w)o(ev)o(er,)14 b(it)f(su\016ces)i(that)f(these)i(b)q
(e)e(met)f(when)i(an)e(appropriate)h(compilation)d(\015ag)j(is)f(sp)q
(eci\014ed.)0 872 y Fp(\(I)q(I)q(I\))21 b Fo(An)o(y)e(giv)o(en)g(p)q
(oin)o(ter)h(is)f(stored)h(in)f(con)o(tiguous)h(memory)m(,)d(or)i(in)g
(lo)q(cations)g(that)h(can)f(b)q(e)i(recognized)f(b)o(y)f(the)104
921 y(collector)14 b(as)g(related.)0 1004 y Fp(\(A\))20
b Fo(The)12 b(compiler)f(nev)o(er)i(generates)h(co)q(de)e(to)g
(recompute)h(the)f(v)n(alue)g(of)f(a)h(liv)o(e)f(base)h(p)q(oin)o(ter)h
(from)d(a)i(deriv)o(ed)g(p)q(oin)o(ter.)104 1054 y(In)i(other)g(w)o
(ords,)g(all)e(liv)o(e)i(base)g(p)q(oin)o(ters)h(are)f(explicitly)f
(stored)i(at)e(run-time.)0 1137 y Fp(\(C\))20 b Fo(W)m(e)14
b(m)o(ust)f(b)q(e)h(able)g(to)g(de\014ne)h(the)f(macro)f
Fm(KEEP)p 869 1137 14 2 v 15 w(LIVE\()f Fd(e;)7 b(y)q(;)g(t;)g(tmp)14
b Fm(\))p Fo(.)0 1220 y Fp(\(D\))19 b Fo(W)m(e)14 b(m)o(ust)f(b)q(e)h
(able)g(to)g(de\014ne)h(a)e(macro)g Fm(DISGUISED)p 944
1220 V 14 w(ZERO)p Fo(.)62 1312 y(On)21 b(standard)g(RISC)f(arc)o
(hitectures)j(with)d(existing)g(compilers,)h(w)o(e)g(exp)q(ect)h(that)e
(only)g(\(C\))h(and)f(\(D\))h(ma)o(y)d(b)q(e)0 1361 y(problematic.)e(W)
m(e)c(claim)d(that)k(they)f(are)h(easy)f(to)g(supp)q(ort)h(directly)f
(in)g(a)f(compiler)g(bac)o(k-end,)h(or)g(can)h(b)q(e)f(implemen)o(ted)0
1411 y(with)i(a)f(p)q(ostpass)i(on)f(the)g(compiler)f(output.)0
1549 y Fn(Ac)n(kno)n(wledgmen)n(ts)0 1639 y Fo(Revisions)20
b(to)g(earlier)g(v)o(ersions)h(of)e(this)i(prop)q(osal)f(w)o(ere)h
(inspired)f(b)o(y)g([10)o(])g(and)g(discussions)h(with)f(v)n(arious)f
(others,)0 1689 y(including)13 b(Alan)g(Demers,)g(John)h(Ellis,)f(and)h
(Thomas)e(Breuel.)0 1827 y Fn(References)21 1917 y Fo([1])19
b(ANSI.)g Fg(Pr)n(o)n(gr)n(amming)14 b(L)n(anguage)i(C,)e(X3.159-1989)p
Fo(.)19 b(American)13 b(National)g(Standards)h(Institute,)h(1989.)21
2000 y([2])k(Russ)e(A)o(tkinson,)e(Alan)h(Demers,)g(Carl)f(Hauser,)i
(Christian)f(Jacobi,)f(P)o(eter)j(Kessler,)f(and)f(Mark)g(W)m(eiser.)24
b(Exp)q(e-)85 2050 y(riences)17 b(creating)e(a)f(p)q(ortable)h(Cedar.)
21 b Fg(A)o(CM)16 b(SIGPLAN)g(Notic)n(es)p Fo(,)e(24\(7\):322{329,)e
(July)j(1989.)k(Pro)q(ceedings)e(of)85 2100 y(the)e(A)o(CM)f(SIGPLAN)g
('89)e(Conference)k(on)e(Programmi)o(ng)d(Language)i(Design)h(and)g
(Implemen)o(tation.)21 2183 y([3])19 b(Jo)q(el)d(F.)g(Bartlett.)25
b(Compacting)14 b(garbage)i(collection)f(with)h(am)o(biguous)d(ro)q
(ots.)25 b(WRL)15 b(Researc)o(h)i(Rep)q(ort)f(88/2,)85
2233 y(Digital)c(Equipmen)o(t)g(Corp)q(oration)h(W)m(estern)h(Researc)o
(h)h(Lab)q(oratory)m(,)d(F)m(ebruary)i(1988.)i(Also)d(in)g
Fg(Lisp)i(Pointers)e Fo(1,)85 2283 y(6)h(\(April-June)g(1988\),)f(pp.)g
(3{12.)21 2366 y([4])19 b(Jo)q(el)c(F.)e(Bartlett.)19
b(Sc)o(heme)14 b Fq(\))g Fo(C:)f(a)h(p)q(ortable)g(Sc)o(heme-to-C)g
(compiler.)j(WRL)c(Researc)o(h)i(Rep)q(ort)f(89/1,)f(Digital)85
2416 y(Equipmen)o(t)g(Corp)q(oration)g(W)m(estern)i(Researc)o(h)g(Lab)q
(oratory)m(,)e(Jan)o(uary)h(1989.)p eop
%%Page: 12 12
12 11 bop 14 8 a Fo(12)931 b Fh(The)14 b(Journal)g(of)f(C)h(Language)f
(T)m(ranslation)g({)g(REPRINT)p 0 23 1950 2 v 21 154
a Fo([5])19 b(Hans-J.)11 b(Bo)q(ehm,)e(Alan)h(J.)g(Demers,)g(and)g
(Scott)h(Shenk)o(er.)i(Mostly)d(parallel)f(garbage)h(collection.)h
Fg(A)o(CM)h(SIGPLAN)85 203 y(Notic)n(es)p Fo(,)f(26\(6\):157{164,)e
(June)k(1991.)g(Pro)q(ceedings)g(of)e(the)h(A)o(CM)f(SIGPLAN)h('91)e
(Conference)j(on)e(Programming)85 253 y(Language)j(Design)f(and)h
(Implemen)o(tation.)21 336 y([6])19 b(Hans-J.)i(Bo)q(ehm)e(and)h(Mark)h
(W)m(eiser.)37 b(Garbage)20 b(collection)g(in)g(an)g(unco)q(op)q
(erativ)o(e)h(en)o(vironmen)o(t.)36 b Fg(Softwar)n(e)85
386 y(Pr)n(actic)n(e)15 b(and)g(Exp)n(erienc)n(e)p Fo(,)f
(18\(9\):807{820,)d(Septem)o(b)q(er)j(1988.)21 469 y([7])19
b(P)m(.)f(Briggs,)h(K.)f(Co)q(op)q(er,)h(and)f(L.)g(T)m(orczon.)31
b(Rematerialization.)e Fg(A)o(CM)18 b(SIGPLAN)i(Notic)n(es)p
Fo(,)e(27\(7\):311{321,)85 519 y(July)d(1992.)j(Pro)q(ceedings)e(of)e
(the)h(A)o(CM)g(SIGPLAN)f('92)g(Conference)i(on)e(Programming)d
(Language)j(Design)g(and)85 569 y(Implemen)o(tation.)21
652 y([8])19 b(Regis)c(Cridlig.)k(An)c(optimizing)d(ML)j(to)f(C)h
(compiler.)k(In)c Fg(A)o(CM)g(SIGPLAN)h(Workshop)h(on)f(ML)g(and)g(Its)
g(Appli-)85 702 y(c)n(ations)p Fo(,)e(San)g(F)m(rancisco,)f(June)i
(1992.)21 785 y([9])k(L.)c(P)o(eter)i(Deutsc)o(h)f(and)g(Daniel)e(G.)g
(Bobro)o(w.)23 b(An)15 b(e\016cien)o(t)h(incremen)o(tal)f(automatic)e
(garbage)j(collector.)22 b Fg(Com-)85 834 y(munic)n(ations)16
b(of)f(the)f(A)o(CM)p Fo(,)g(19\(9\),)e(Septem)o(b)q(er)j(1976.)0
917 y([10])k(A.)g(Diw)o(an,)g(E.)g(Moss,)h(and)f(R.)f(Hudson.)34
b(Compiler)17 b(supp)q(ort)j(for)f(garbage)g(collection)g(in)f(a)h
(statically)f(t)o(yp)q(ed)85 967 y(language.)d(In)e Fg(Pr)n(o)n(c)n(e)n
(e)n(dings)g(of)h(the)f(A)o(CM)h(SIGPLAN)g('92)g(Confer)n(enc)n(e)f(on)
h(Pr)n(o)n(gr)n(amming)f(L)n(anguage)i(Design)f(and)85
1017 y(Implementation)p Fo(,)g(n)o(um)o(b)q(er)f(7)h(in)f(SIGPLAN)h
(Notices)h(27,)e(pages)h(273{282,)e(July)h(1992.)0 1100
y([11])19 b(Daniel)14 b(Edelson.)22 b(A)15 b(mark-and-sw)o(eep)f
(collector)i(for)e(C)p Fm(++)p Fo(.)21 b(In)15 b Fg(Confer)n(enc)n(e)h
(R)n(e)n(c)n(or)n(d)g(of)f(the)h(Ninete)n(enth)g(A)o(nnual)85
1150 y(A)o(CM)f(SIGPLAN-SIGA)o(CT)g(Symp)n(osium)g(on)h(Principles)e
(of)h(Pr)n(o)n(gr)n(amming)f(L)n(anguages)p Fo(,)g(pages)h(51{58,)d
(1992.)0 1233 y([12])19 b(Reed)c(Hastings)e(and)h(Bob)g(Jo)o(yce.)k(F)m
(ast)c(detection)h(of)e(memory)e(leaks)j(and)f(access)j(errors.)j(In)14
b Fg(Pr)n(o)n(c)n(e)n(e)n(dings)g(of)h(the)85 1283 y(Winter)g('92)g
(USENIX)g(c)n(onfer)n(enc)n(e)p Fo(,)f(pages)g(125{136,)e(1992.)0
1366 y([13])19 b(Stephen)c(M.)f(Omoh)o(undro.)j Fg(The)d(Sather)h(L)n
(anguage)p Fo(.)20 b(ICSI,)13 b(Berk)o(eley)m(,)h(1991.)0
1449 y([14])19 b(John)d(R.)e(Rose)i(and)f(Hans)h(Muller.)23
b(In)o(tegrating)15 b(the)h(Sc)o(heme)f(and)g(C)h(languages.)22
b(In)15 b Fg(Pr)n(o)n(c)n(e)n(e)n(dings)h(of)h(the)f(1992)85
1499 y(A)o(CM)f(Confer)n(enc)n(e)g(on)g(Lisp)g(and)h(F)m(unctional)f
(Pr)n(o)n(gr)n(amming)p Fo(,)e(pages)h(247{259,)e(1992.)0
1582 y([15])19 b(P)o(aul)c(Ro)o(vner.)20 b(On)c(adding)e(garbage)g
(collection)h(and)f(run)o(time)g(t)o(yp)q(es)i(to)f(a)f(strongly-t)o
(yp)q(ed,)h(statically)f(c)o(hec)o(k)o(ed,)85 1631 y(concurren)o(t)i
(language.)h(T)m(ec)o(hnical)d(Rep)q(ort)g(CSL-84-7,)e(Xero)o(x)i(P)o
(alo)f(Alto)h(Researc)o(h)h(Cen)o(ter,)f(1984.)0 1714
y([16])19 b(W.)13 b(F.)h(Sc)o(helter)h(and)f(M.)f(Ballan)o(t)o(yne.)k
(Ky)o(oto)d(Commo)o(n)d(Lisp.)18 b Fg(AI)d(Exp)n(ert)p
Fo(,)e(3\(3\):75{77,)f(1988.)0 1797 y([17])19 b(Benjamin)10
b(Zorn.)k(The)d(measured)g(cost)h(of)f(conserv)n(ativ)o(e)g(garbage)g
(collection.)i(Departmen)o(t)e(of)f(Computer)h(Science)85
1847 y(T)m(ec)o(hnical)j(Rep)q(ort)g(CU-CS-573-92,)e(Univ)o(ersit)o(y)i
(of)f(Colorado)g(at)g(Boulder,)h(1992.)0 1963 y Fh(Hans-J.)g(Bo)q(ehm)f
(is)g(a)h(mem)o(b)q(er)e(of)h(the)h(researc)o(h)h(sta\013)f(at)g(the)g
(Xero)o(x)g(P)o(alo)f(Alto)g(Researc)o(h)i(Cen)o(ter,)f(in)f(the)i
(Computer)0 2013 y(Science)i(Lab)q(oratory)m(.)k(Previously)15
b(he)g(taugh)o(t)g(at)g(the)h(Univ)o(ersit)o(y)f(of)g(W)m(ashington)f
(and)h(at)g(Rice)g(Univ)o(ersit)o(y)m(.)21 b(He)16 b(has)0
2063 y(a)f(Ph.D.)f(in)h(Computer)f(Science)j(from)c(Cornell)i(Univ)o
(ersit)o(y)m(.)21 b(He)16 b(can)f(b)q(e)h(reac)o(hed)h(as)e
Fo(b)q(o)q([email protected])o(x.com)e Fh(or)i(at)0 2113
y(+1)f(415)f(812)g(4435.)62 2163 y(Da)o(vid)i(Chase)i(is)f(a)g(sta\013)
g(engineer)h(w)o(orking)e(on)h(compilers)f(at)h(SunPro,)h(a)f(business)
h(of)e(Sun)i(Microsystems,)f(Inc.)0 2213 y(in)k(Moun)o(tain)f(View.)37
b(He)21 b(has)f(a)g(Ph.D.)f(from)g(Rice)h(Univ)o(ersit)o(y)m(.)36
b(He)21 b(can)f(b)q(e)h(reac)o(hed)h(at)e(+1)g(415)f(336)h(1587)f(or)0
2262 y Fo(dc)o([email protected])p Fh(.)950 2354 y Fa(1)p
eop
%%Trailer
end
userdict /end-hook known{end-hook}if
%%EOF


  3 Responses to “Category : C Source Code
Archive   : BOEHMGC.ZIP
Filename : BOECHA.PS

  1. Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!

  2. This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.

  3. But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/