thfs.c - plan9port - [fork] Plan 9 from user space
HTML git clone git://src.adamsgaard.dk/plan9port
DIR Log
DIR Files
DIR Refs
DIR README
DIR LICENSE
---
thfs.c (55378B)
---
1 /*
2 Copyright (c) 2007 David Swasey; see COPYRIGHT.
3 Limitations:
4 Hfsreaddir skips entries whose names contain NUL.
5 Hfsbadblock is untested.
6 */
7
8 #include <u.h>
9 #include <libc.h>
10 #include <thread.h>
11 #include <sunrpc.h>
12 #include <nfs3.h>
13 #include <diskfs.h>
14 #include "hfs.h"
15
16 #define debug 0
17
18 static char Rprefix[] = "._";
19 enum { Rplen = nelem(Rprefix)-1 };
20
21 static int hfssync(Fsys*);
22 static int hfswrapper(Fsys*);
23 static int hfstreesync(Hfs*, Fork*, Tree*, int);
24 static u32int hfsmetadir(Hfs*);
25 static void hfsclose(Fsys*);
26 static Block* hfsblockread(Fsys*, u64int);
27
28 static Nfs3Status hfsroot(Fsys*, Nfs3Handle*);
29 static Nfs3Status hfsgetattr(Fsys*, SunAuthUnix*, Nfs3Handle*, Nfs3Attr*);
30 static Nfs3Status hfsaccess(Fsys *fsys, SunAuthUnix*, Nfs3Handle *, u32int, u32int*, Nfs3Attr *attr);
31 static Nfs3Status hfslookup(Fsys*, SunAuthUnix*, Nfs3Handle*, char*, Nfs3Handle*);
32 static Nfs3Status _hfslookup(Hfs*, u32int, char*, Treeref*);
33 static Nfs3Status hfsreaddir(Fsys *fsys, SunAuthUnix*, Nfs3Handle *h, u32int, u64int, uchar**, u32int*, u1int*);
34 static Nfs3Status hfsreadfile(Fsys*, SunAuthUnix*, Nfs3Handle*, u32int, u64int, uchar**, u32int*, u1int*);
35 static Nfs3Status hfsreadlink(Fsys*, SunAuthUnix*, Nfs3Handle*, char**);
36
37 static int hfsextentsearch(Hfs*, u32int, int, u32int, u32int*, Extent*);
38 static int hfscatsearch(Hfs*, Catalogkey*, Treeref*);
39 static int _hfscatalogkeycmp(uchar*, int, int*, Key*, int);
40 static int hfstreesearch(Tree*, Key*, int*, Treeref*);
41 static void hfsref(Tree*, Treeref*);
42 static void hfsrefput(Treeref*);
43 static int hfsrefnode(Treeref*, u32int);
44 static int hfsrefrec(Treeref*, int);
45 static int hfsrefnextrec(Treeref*);
46
47 static int hfsforkread(Hfs*, Fork*, uchar*, u32int, u64int);
48 static Block* hfsforkblock(Hfs*, Fork*, u32int);
49 static Block* hfsblock(Hfs*, u32int);
50
51 static void getnodedesc(Node*, uchar*);
52 static void getfork(Fork*, u32int, int, uchar*);
53 static void getextents(Extent*, uchar*);
54 static void getextent(Extent*, uchar*);
55 static int getextentkey(Extentkey*, uchar*, int);
56 static int getcatalogrecord(Inode*, uchar*, int);
57 static int getcatalogthread(Catalogkey*, uchar*, int);
58 static int getcatalogkey(Catalogkey*, uchar*, int, int);
59 static int getname(Name*, uchar*);
60 static u32int gettime(uchar*);
61 static u64int get64(uchar*);
62 static u32int get32(uchar*);
63 static int get16(uchar*);
64 static void put32(uchar*, u32int);
65
66 static int hfsinamecmp(Name*, Name*);
67 static int hfsnamecmp(Name*, Name*);
68
69 Fsys*
70 fsysopenhfs(Disk *disk)
71 {
72 Hfs *fs;
73 Fsys *fsys;
74
75 fsys = emalloc(sizeof(Fsys));
76 fs = emalloc(sizeof(Hfs));
77 fsys->priv = fs;
78 fs->fsys = fsys;
79 fs->disk = disk;
80 fsys->type = "hfs";
81 fsys->_readblock = hfsblockread;
82 fsys->_sync = hfssync;
83 fsys->_root = hfsroot;
84 fsys->_getattr = hfsgetattr;
85 fsys->_access = hfsaccess;
86 fsys->_lookup = hfslookup;
87 fsys->_readfile = hfsreadfile;
88 fsys->_readlink = hfsreadlink;
89 fsys->_readdir = hfsreaddir;
90 fsys->_close = hfsclose;
91 fsys->disk = disk;
92
93 if(hfswrapper(fsys) < 0 || hfssync(fsys) < 0)
94 goto error;
95
96 return fsys;
97
98 error:
99 hfsclose(fsys);
100 return nil;
101 }
102
103 static void
104 hfsclose(Fsys *fsys)
105 {
106 Hfs *fs;
107
108 fs = fsys->priv;
109 /*
110 * We're not supposed to close the disk passed to
111 * hfsopen, but if we created our own partition disk
112 * we need to close that. It will close its subdisk
113 * unless we call diskpartabandon. Bad planning.
114 */
115 if(fs->disk && fs->disk != fsys->disk){
116 diskpartabandon(fs->disk);
117 diskclose(fs->disk);
118 }
119 free(fs);
120 free(fsys);
121 }
122
123 static int
124 hfswrapper(Fsys *fsys)
125 {
126 Hfs *fs;
127 Disk *disk;
128 Block *b;
129 uchar *mdb;
130 int magic, hfsstart, subsig, substart, subnblocks;
131 u32int hfsblocksize;
132 u64int offset, size;
133
134 fs = fsys->priv;
135 disk = fsys->disk;
136 if((b = diskread(disk, 162, 1024)) == nil)
137 return -1;
138 mdb = b->data;
139 magic = get16(mdb);
140 hfsblocksize = get32(mdb+20);
141 hfsstart = get16(mdb+28);
142 subsig = get16(mdb+124);
143 substart = get16(mdb+126);
144 subnblocks = get16(mdb+128);
145 blockput(b);
146
147 if(magic != Hfssig)
148 return 0;
149 if(subsig != Hfsplussig && subsig != Hfsxsig)
150 return 0;
151
152 offset = hfsstart*512 + substart*hfsblocksize;
153 size = subnblocks*hfsblocksize;
154
155 if((fs->disk = diskpart(disk, offset, size)) == nil)
156 return -1;
157 if(debug) fprint(2, "wrapped hfs size 0x%ullx offset 0x%ullx\n", size, offset);
158 return 0;
159 }
160
161 static int
162 checkvolhdr(uchar *vh)
163 {
164 u32int magic;
165
166 magic = get32(vh);
167 switch(magic){
168 case Hfsplusmagic:
169 return 0;
170 case Hfsxmagic:
171 return 1;
172 default:
173 werrstr("bad volume header magic 0x%ux", magic);
174 return -1;
175 }
176 }
177
178 static int
179 hfssync(Fsys *fsys)
180 {
181 Hfs *fs;
182 Disk *disk;
183 Block *b;
184 uchar *vh;
185 int sensitive;
186
187 fs = fsys->priv;
188 disk = fs->disk;
189
190 if((b = diskread(disk, 512, 1024)) == nil)
191 goto error;
192 vh = b->data;
193 if((sensitive = checkvolhdr(vh)) < 0)
194 goto error;
195 fs->blocksize = get32(vh+40);
196 fs->nblock = get32(vh+44);
197 fs->nfree = get32(vh+48);
198 fs->hasbadblocks = get32(vh+4) & (1<<9);
199 getfork(&fs->alloc, AllocId, Dfork, vh+112);
200 getfork(&fs->extentsfork, ExtentsId, Dfork, vh+192);
201 getfork(&fs->catalogfork, CatalogId, Dfork, vh+272);
202 blockput(b);
203 b = nil;
204
205 if(hfstreesync(fs, &fs->extentsfork, &fs->extents, 0) < 0)
206 goto error;
207 if(hfstreesync(fs, &fs->catalogfork, &fs->catalog, sensitive) < 0)
208 goto error;
209 fs->hlinkparent = hfsmetadir(fs);
210
211 fsys->blocksize = fs->blocksize;
212 fsys->nblock = fs->nblock;
213 if(debug) fprint(2, "hfs %ud %ud-byte blocks (%ud free, %s bad)\n",
214 fs->nblock, fs->blocksize, fs->nfree, fs->hasbadblocks?"some":"none");
215 return 0;
216
217 error:
218 blockput(b);
219 return -1;
220 }
221
222 static int
223 hfstreesync(Hfs *fs, Fork *fork, Tree *tree, int sensitive)
224 {
225 Block *b;
226 uchar *hr;
227 Node node;
228
229 b = nil;
230 if(fork->extent[0].count == 0){
231 if(debug) fprint(2, "tree fork empty\n");
232 goto error;
233 }
234 if((b = hfsblock(fs,fork->extent[0].start)) == nil)
235 goto error;
236 getnodedesc(&node, b->data);
237 if(node.type != HeaderNode){
238 if(debug) fprint(2, "bad header node type %d\n", node.type);
239 goto error;
240 }
241 hr = b->data+Ndlen;
242 tree->nodesize = get16(hr+18);
243 tree->nnodes = get32(hr+22);
244 tree->root = get32(hr+2);
245 tree->height = get16(hr);
246 tree->maxkeylen = get16(hr+20);
247 tree->indexkeylen = (get32(hr+38)&4) ? 0 : tree->maxkeylen;
248 tree->sensitive = sensitive && hr[37]==0xBC;
249 blockput(b);
250 tree->fs = fs;
251 tree->fork = fork;
252 if(debug) fprint(2, "tree %ud %ud %d-byte nodes\n",
253 fork->cnid, tree->nnodes, tree->nodesize);
254 return 0;
255
256 error:
257 werrstr("bad tree %ud header", fork->cnid);
258 blockput(b);
259 return -1;
260 }
261
262 static u32int
263 hfsmetadir(Hfs *fs)
264 {
265 static Rune name[] = {0,0,0,0,'H','F','S','+',' ','P','r','i','v','a','t','e',' ','D','a','t','a'};
266 Catalogkey key;
267 Treeref ref;
268 Inode ino;
269
270 key.parent = RootId;
271 key.u.name.len = nelem(name);
272 memcpy(key.u.name.name, name, sizeof name);
273 if(hfscatsearch(fs, &key, &ref) < 0)
274 goto notfound;
275 if(getcatalogrecord(&ino, ref.data, ref.dlen) < 0)
276 goto notfound;
277 if((ino.mode&IFMT) != IFDIR)
278 goto notfound;
279 hfsrefput(&ref);
280 if(debug) fprint(2, "metadata directory %ud\n", ino.cnid);
281 return ino.cnid;
282
283 notfound:
284 if(debug) fprint(2, "metadata directory not found\n");
285 hfsrefput(&ref);
286 return 0;
287 }
288
289 static int
290 hfsbadblock(Hfs *fs, u32int bno)
291 {
292 Extent e[NEXTENTS];
293 int i;
294
295 if(hfsextentsearch(fs, BadblockId, Dfork, bno, nil, e) < 0)
296 return 0;
297 /*
298 Don't lightly throw away a block.
299 */
300 for(i=0; i<NEXTENTS; i++)
301 if(e[i].start <= bno && bno < e[i].start+e[i].count)
302 return 1;
303 if(debug) fprint(2, "corrupt badblock record, block %ud\n", bno);
304 return 0;
305 }
306
307 static Block*
308 hfsblockread(Fsys *fsys, u64int vbno)
309 {
310 Hfs *fs;
311 u32int bno;
312 Block *b;
313 int n, alloc;
314
315 fs = fsys->priv;
316 if(vbno >= fs->nblock){
317 if(debug) fprint(2, "block %llud past end of volume\n", vbno);
318 return nil;
319 }
320 bno = vbno;
321
322 n = bno>>3;
323 if((b = hfsforkblock(fs, &fs->alloc, n/fs->blocksize)) == nil){
324 if(debug) fprint(2, "can't read alloc bitmap for block %ud\n", bno);
325 /* assume it's used */
326 }
327 else{
328 alloc = b->data[n%fs->blocksize] & (1<<(7-(bno&7)));
329 blockput(b);
330 if(!alloc)
331 return nil;
332 }
333
334 if(fs->hasbadblocks && hfsbadblock(fs, bno)){
335 if(debug) fprint(2, "bad block %ud\n", bno);
336 return nil;
337 }
338
339 b = hfsblock(fs, bno);
340 if(debug && b == nil) fprint(2, "can't read block %ud\n", bno);
341 return b;
342 }
343
344 static int
345 hasresource(Inode *ino)
346 {
347 return (ino->mode&IFMT)==IFREG && ino->u.f.rfork.size>0;
348 }
349
350 static void
351 useresource(Inode *ino)
352 {
353 ino->fileid = ((u64int)1)<<32 | ino->cnid;
354 ino->u.f.nhdr = Adlen;
355 ino->u.f.fork = &ino->u.f.rfork;
356 }
357
358 static int
359 ref2ino(Hfs *fs, Treeref *ref, Inode *ino)
360 {
361 static uchar magic[] = {'h','l','n','k','h','f','s','+'};
362 Catalogkey key;
363 Treeref hlink;
364 u32int cnid;
365
366 if(getcatalogrecord(ino, ref->data, ref->dlen) < 0)
367 return -1;
368
369 if((ino->mode&IFMT) == IFREG
370 && memcmp(ino->u.f.info, magic, nelem(magic)) == 0){
371 if(debug) print("iNode%ud...", ino->special);
372 if(fs->hlinkparent == 0)
373 return -1;
374 key.parent = fs->hlinkparent;
375 key.u.name.len = runesnprint(key.u.name.name, sizeof key.u.name.name,
376 "iNode%ud", ino->special);
377 if(hfscatsearch(fs, &key, &hlink) < 0)
378 goto error;
379 cnid = ino->cnid;
380 if(getcatalogrecord(ino, hlink.data, hlink.dlen) < 0)
381 goto error;
382 hfsrefput(&hlink);
383 ino->cnid = cnid;
384 ino->fileid = cnid;
385 ino->nlink = ino->special;
386 }
387 return 0;
388
389 error:
390 hfsrefput(&hlink);
391 return -1;
392 }
393
394 static void
395 mkhandle(Nfs3Handle *h, int rsrc, u32int cnid)
396 {
397 h->h[0] = rsrc;
398 put32(h->h+1, cnid);
399 h->len = 5;
400 }
401
402 static Nfs3Status
403 hfsroot(Fsys *fsys, Nfs3Handle *h)
404 {
405 USED(fsys);
406 mkhandle(h, 0, RootId);
407 return Nfs3Ok;
408 }
409
410 static Nfs3Status
411 handle2ino(Hfs *fs, Nfs3Handle *h, Treeref *ref, Catalogkey *key, Inode *ino)
412 {
413 Treeref refbuf;
414 u32int cnid;
415 Catalogkey keybuf;
416 int rsrc;
417
418 if(h->len != 5)
419 return Nfs3ErrBadHandle;
420 rsrc = h->h[0];
421 cnid = get32(h->h+1);
422 if(debug) print("cnid %ud%s...", cnid, rsrc ? " rsrc" : "");
423
424 if(ref == nil)
425 ref = &refbuf;
426 if(key == nil)
427 key = &keybuf;
428
429 /* map cnid to full catalog key */
430 key->parent = cnid;
431 key->u.name.len = 0;
432 if(hfscatsearch(fs, key, ref) < 0)
433 goto error;
434 if(getcatalogthread(key, ref->data, ref->dlen) < 0)
435 goto error;
436 hfsrefput(ref);
437
438 if(debug) print("{%ud,%.*S}...", key->parent, key->u.name.len, key->u.name.name);
439
440 /* map full key to catalog info */
441 if(hfscatsearch(fs, key, ref) < 0)
442 goto error;
443 if(ino != nil){
444 if(ref2ino(fs, ref, ino) < 0)
445 goto error;
446 if(rsrc){
447 if(!hasresource(ino)){
448 hfsrefput(ref);
449 return Nfs3ErrBadHandle;
450 }
451 useresource(ino);
452 }
453 }
454 if(ref == &refbuf)
455 hfsrefput(ref);
456
457 return Nfs3Ok;
458
459 error:
460 hfsrefput(ref);
461 return Nfs3ErrIo;
462 }
463
464 static Nfs3Status
465 ino2attr(Hfs *fs, Inode *ino, Nfs3Attr *attr)
466 {
467 u32int rdev;
468
469 switch(ino->mode&IFMT){
470 case IFIFO:
471 attr->type = Nfs3FileFifo;
472 break;
473 case IFCHR:
474 attr->type = Nfs3FileChar;
475 break;
476 case IFDIR:
477 attr->type = Nfs3FileDir;
478 break;
479 case IFBLK:
480 attr->type = Nfs3FileBlock;
481 break;
482 case IFREG:
483 attr->type = Nfs3FileReg;
484 break;
485 case IFLNK:
486 attr->type = Nfs3FileSymlink;
487 break;
488 case IFSOCK:
489 attr->type = Nfs3FileSocket;
490 break;
491 case IFWHT:
492 default:
493 if(debug) fprint(2, "bad format %uo\n", ino->mode&IFMT);
494 return Nfs3ErrBadHandle;
495 }
496
497 attr->mode = ino->mode&07777;
498 attr->nlink = ino->nlink;
499 attr->uid = ino->uid;
500 attr->gid = ino->gid;
501 if(attr->type==Nfs3FileReg || attr->type==Nfs3FileSymlink){
502 attr->size = ino->u.f.nhdr+ino->u.f.fork->size;
503 attr->used = (u64int)ino->u.f.fork->nblocks*fs->blocksize;
504 }
505 else{
506 attr->size = 0;
507 attr->used = 0;
508 }
509 if(attr->type==Nfs3FileBlock || attr->type==Nfs3FileChar){
510 rdev = ino->special;
511 attr->major = (rdev>>8)&0xFF; /* not mentioned in the tech note */
512 attr->minor = rdev & 0xFFFF00FF;
513 }else{
514 attr->major = 0;
515 attr->minor = 0;
516 }
517 attr->fsid = 0;
518 attr->fileid = ino->fileid;
519 attr->atime.sec = ino->atime;
520 attr->atime.nsec = 0;
521 attr->mtime.sec = ino->mtime;
522 attr->mtime.nsec = 0;
523 attr->ctime.sec = ino->ctime;
524 attr->ctime.nsec = 0;
525 return Nfs3Ok;
526 }
527
528 static int
529 ingroup(SunAuthUnix *au, uint gid)
530 {
531 int i;
532
533 for(i=0; i<au->ng; i++)
534 if(au->g[i] == gid)
535 return 1;
536 return 0;
537 }
538
539 static Nfs3Status
540 inoperm(Inode *ino, SunAuthUnix *au, int need)
541 {
542 int have;
543
544 if(allowall)
545 return Nfs3Ok;
546
547 have = ino->mode&0777;
548 if(ino->uid == au->uid)
549 have >>= 6;
550 else if(ino->gid == au->gid || ingroup(au, ino->gid))
551 have >>= 3;
552
553 if((have&need) != need)
554 return Nfs3ErrNotOwner; /* really EPERM */
555 return Nfs3Ok;
556 }
557
558 static Nfs3Status
559 hfsgetattr(Fsys *fsys, SunAuthUnix *au, Nfs3Handle *h, Nfs3Attr *attr)
560 {
561 Inode ino;
562 Hfs *fs;
563 Nfs3Status ok;
564
565 fs = fsys->priv;
566 if((ok = handle2ino(fs, h, nil, nil, &ino)) != Nfs3Ok)
567 return ok;
568
569 USED(au); /* anyone can getattr */
570 return ino2attr(fs, &ino, attr);
571 }
572
573 static Nfs3Status
574 hfsaccess(Fsys *fsys, SunAuthUnix *au, Nfs3Handle *h, u32int want, u32int *got, Nfs3Attr *attr)
575 {
576 int have;
577 Inode ino;
578 Hfs *fs;
579 Nfs3Status ok;
580
581 fs = fsys->priv;
582 if((ok = handle2ino(fs, h, nil, nil, &ino)) != Nfs3Ok)
583 return ok;
584
585 have = ino.mode&0777;
586 if(ino.uid == au->uid)
587 have >>= 6;
588 else if(ino.gid == au->gid || ingroup(au, ino.gid))
589 have >>= 3;
590
591 *got = 0;
592 if((want&Nfs3AccessRead) && (have&AREAD))
593 *got |= Nfs3AccessRead;
594 if((want&Nfs3AccessLookup) && (ino.mode&IFMT)==IFDIR && (have&AEXEC))
595 *got |= Nfs3AccessLookup;
596 if((want&Nfs3AccessExecute) && (ino.mode&IFMT)!=IFDIR && (have&AEXEC))
597 *got |= Nfs3AccessExecute;
598
599 return ino2attr(fs, &ino, attr);
600 }
601
602 static Nfs3Status
603 utf2name(Name *n, char *name)
604 {
605 int len;
606 Rune *p;
607
608 p = n->name;
609 len = 0;
610 while(*name){
611 if(len == NAMELEN)
612 return Nfs3ErrNameTooLong;
613 name += chartorune(p, name);
614 if(*p == ':')
615 *p = '/'; /* not mentioned in the tech note */
616 p++;
617 len++;
618 }
619 n->len = len;
620 return Nfs3Ok;
621 }
622
623 static int
624 name2utf(char *buf, Name *name)
625 {
626 int len, i;
627
628 len = 0;
629 for(i=0; i<name->len; i++){
630 if(name->name[i] == '/'){ /* not mentioned in the tech note */
631 buf[len] = ':';
632 len++;
633 }
634 else
635 len += runetochar(buf+len, name->name+i);
636 }
637 return len;
638 }
639
640 static Nfs3Status
641 hfslookup(Fsys *fsys, SunAuthUnix *au, Nfs3Handle *h, char *name, Nfs3Handle *nh)
642 {
643 Hfs *fs;
644 Inode ino, target;
645 Nfs3Status ok;
646 Catalogkey key;
647 Treeref ref;
648 int rsrc;
649
650 fs = fsys->priv;
651 if((ok = handle2ino(fs, h, nil, &key, &ino)) != Nfs3Ok)
652 return ok;
653
654 if((ino.mode&IFMT) != IFDIR)
655 return Nfs3ErrNotDir;
656
657 if((ok = inoperm(&ino, au, AEXEC)) != Nfs3Ok)
658 return ok;
659
660 if(strcmp(name, ".") == 0){
661 mkhandle(nh, 0, ino.cnid);
662 return Nfs3Ok;
663 }
664 if(strcmp(name, "..") == 0){
665 mkhandle(nh, 0, key.parent);
666 return Nfs3Ok;
667 }
668
669 rsrc = 0;
670 if((ok = _hfslookup(fs, ino.cnid, name, &ref)) != Nfs3Ok){
671 if(memcmp(name, Rprefix, Rplen)==0
672 && _hfslookup(fs, ino.cnid, name+Rplen, &ref)==Nfs3Ok)
673 rsrc = 1;
674 else
675 return ok;
676 }
677 if(ref2ino(fs, &ref, &target) < 0)
678 goto error;
679 hfsrefput(&ref);
680 if(rsrc && !hasresource(&target))
681 return Nfs3ErrNoEnt;
682 mkhandle(nh, rsrc, target.cnid);
683 return Nfs3Ok;
684
685 error:
686 hfsrefput(&ref);
687 return Nfs3ErrIo;
688 }
689
690 static Nfs3Status
691 _hfslookup(Hfs *fs, u32int parent, char *name, Treeref *ref)
692 {
693 Catalogkey key;
694 Nfs3Status ok;
695
696 key.parent = parent;
697 if((ok = utf2name(&key.u.name, name)) != Nfs3Ok)
698 return ok;
699 if(hfscatsearch(fs, &key, ref) < 0)
700 return Nfs3ErrNoEnt;
701 return Nfs3Ok;
702 }
703
704
705 /*
706 For the moment, hfsreaddir does not return entries whose names
707 contain NUL, avoiding errors like "ls: : No such file or
708 directory" when listing a mounted root.
709 */
710 static int
711 hfshidename(Name *n)
712 {
713 int i;
714
715 for(i=0; i<n->len; i++)
716 if(n->name[i] == 0)
717 return 1;
718 return 0;
719 }
720
721 static Nfs3Status
722 hfsreaddir(Fsys *fsys, SunAuthUnix *au, Nfs3Handle *h, u32int count,
723 u64int cookie, uchar **pdata, u32int *pcount, u1int *peof)
724 {
725 Nfs3Handle ch;
726 u32int i, cnid;
727 Treeref ref;
728 Catalogkey key;
729 Nfs3Entry e;
730 int rsrc;
731 char name[Rplen+UTFNAMELEN];
732 uchar *dp, *dep, *ndp, *data;
733 Hfs *fs;
734 Inode ino, child;
735 Nfs3Status ok;
736 u32int nentries;
737
738 fs = fsys->priv;
739 if((ok = handle2ino(fs, h, nil, nil, &ino)) != Nfs3Ok)
740 return ok;
741
742 if((ino.mode&IFMT) != IFDIR)
743 return Nfs3ErrNotDir;
744
745 if((ok = inoperm(&ino, au, AREAD)) != Nfs3Ok)
746 return ok;
747
748 if(ino.u.nentries>>31)
749 return Nfs3ErrIo;
750 nentries = ino.u.nentries*2; /* even data, odd resource */
751
752 i = cookie>>32;
753 cnid = cookie&0xFFFFFFFF;
754 if(debug) print("readdir %ud %ud %ud...", cnid, i, nentries);
755 if(i >= nentries){
756 *peof = 1;
757 *pcount = 0;
758 *pdata = nil;
759 return Nfs3Ok;
760 }
761
762 dp = mallocz(count, 1);
763 if(dp == nil)
764 return Nfs3ErrNoMem;
765 data = dp;
766 dep = dp+count;
767
768 /*
769 The catalog order relation ensures that records for a
770 dir's children are contiguous and preceded by its
771 thread record.
772 */
773 if(cnid == 0){
774 key.parent = ino.cnid;
775 key.u.name.len = 0;
776 if(hfscatsearch(fs, &key, &ref) < 0)
777 goto error;
778 }
779 else{
780 mkhandle(&ch, i&1, cnid);
781 if((ok = handle2ino(fs, &ch, &ref, &key, &child)) != Nfs3Ok)
782 return ok;
783 if(key.parent != ino.cnid)
784 goto badparent;
785 i++;
786 }
787
788 memset(&e, 0, sizeof e);
789 for(; i<nentries; i++){
790 rsrc = i&1;
791 if(!rsrc){
792 if(hfsrefnextrec(&ref) < 0)
793 goto error;
794 if(getcatalogkey(&key, ref.key, ref.klen, 1) < 0)
795 goto error;
796 if(key.parent != ino.cnid)
797 goto badparent;
798 if(ref2ino(fs, &ref, &child) < 0)
799 goto error;
800 }
801 else if(!hasresource(&child))
802 continue;
803 else
804 useresource(&child);
805 if(hfshidename(&key.u.name))
806 continue;
807 e.fileid = child.fileid;
808 e.name = name;
809 if(rsrc){
810 memcpy(name, Rprefix, Rplen);
811 e.namelen = Rplen+name2utf(name+Rplen, &key.u.name);
812 }
813 else
814 e.namelen = name2utf(name, &key.u.name);
815 e.cookie = ((u64int)i)<<32 | child.cnid;
816 e.haveAttr = (ino2attr(fs, &child, &e.attr) == Nfs3Ok);
817 e.haveHandle = 1;
818 mkhandle(&e.handle, rsrc, child.cnid);
819 if(debug) print("%s/0x%llux ", e.name, e.fileid);
820 if(nfs3entrypack(dp, dep, &ndp, &e) < 0)
821 break;
822 dp = ndp;
823 }
824 hfsrefput(&ref);
825 if(i == nentries)
826 *peof = 1;
827 *pcount = dp - data;
828 *pdata = data;
829 return Nfs3Ok;
830
831 badparent:
832 if(debug) fprint(2, "%.*S: bad parent %ud != %ud\n",
833 key.u.name.len, key.u.name.name, key.parent, ino.cnid);
834 error:
835 hfsrefput(&ref);
836 return Nfs3ErrIo;
837 }
838
839 /* See RFC 1740. */
840 static int
841 appledouble(Inode *ino, uchar *ad)
842 {
843 static uchar Adhdr[Adlen-4-Filen] =
844 {
845 0,5,22,7,0,2,0,0, /* magic */
846 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, /* filler */
847 0,2, /* nentries */
848 0,0,0,9, /* magic: finder info */
849 0,0,0,Fioff, /* offset */
850 0,0,0,Filen, /* length */
851 0,0,0,2, /* magic: rfork */
852 0,0,0,Adlen, /* offset */
853 };
854
855 if(ino->u.f.rfork.size>>32){
856 if(debug) fprint(2, "resource fork %ud too large\n", ino->cnid);
857 return -1;
858 }
859 memcpy(ad, Adhdr, nelem(Adhdr));
860 put32(ad+nelem(Adhdr), ino->u.f.rfork.size);
861 memcpy(ad+Fioff, ino->u.f.info, Filen);
862 return 0;
863 }
864
865 static Nfs3Status
866 hfsreadfile(Fsys *fsys, SunAuthUnix *au, Nfs3Handle *h, u32int count,
867 u64int offset, uchar **pdata, u32int *pcount, u1int *peof)
868 {
869 u64int size;
870 int skip;
871 uchar *data, prefix[Adlen];
872 Hfs *fs;
873 Inode ino;
874 Nfs3Status ok;
875
876 fs = fsys->priv;
877 if((ok = handle2ino(fs, h, nil, nil, &ino)) != Nfs3Ok)
878 return ok;
879
880 if((ino.mode&IFMT) != IFREG)
881 return Nfs3ErrInval;
882
883 if((ok = inoperm(&ino, au, AREAD)) != Nfs3Ok)
884 return ok;
885
886 size = ino.u.f.nhdr+ino.u.f.fork->size;
887 if(offset >= size){
888 *pdata = 0;
889 *pcount = 0;
890 *peof = 1;
891 return Nfs3Ok;
892 }
893 if(offset+count > size)
894 count = size-offset;
895 data = mallocz(count, 1);
896 if(data == nil)
897 return Nfs3ErrNoMem;
898 if(offset < ino.u.f.nhdr){
899 if(appledouble(&ino, prefix) < 0)
900 goto error;
901 skip = Adlen-offset;
902 if(skip > count)
903 skip = count;
904 memcpy(data, prefix+offset, skip);
905 offset = 0;
906 }
907 else{
908 offset -= ino.u.f.nhdr;
909 skip = 0;
910 }
911 if(hfsforkread(fs, ino.u.f.fork, data+skip, count-skip, offset) < 0)
912 goto error;
913
914 *peof = (offset+count == size);
915 *pcount = count;
916 *pdata = data;
917 return Nfs3Ok;
918
919 error:
920 free(data);
921 return Nfs3ErrIo;
922 }
923
924 static Nfs3Status
925 hfsreadlink(Fsys *fsys, SunAuthUnix *au, Nfs3Handle *h, char **link)
926 {
927 int len;
928 uchar *data;
929 Hfs *fs;
930 Nfs3Status ok;
931 Inode ino;
932
933 fs = fsys->priv;
934 if((ok = handle2ino(fs, h, nil, nil, &ino)) != Nfs3Ok)
935 return ok;
936
937 if((ino.mode&IFMT) != IFLNK)
938 return Nfs3ErrInval;
939
940 if((ok = inoperm(&ino, au, AREAD)) != Nfs3Ok)
941 return ok;
942
943 len = ino.u.f.dfork.size;
944 if(len > 10240) /* arbitrary limit */
945 return Nfs3ErrIo;
946
947 data = mallocz(len+1, 1);
948 if(data == nil)
949 return Nfs3ErrNoMem;
950 if(hfsforkread(fs, &ino.u.f.dfork, data, len, 0) < 0){
951 free(data);
952 return Nfs3ErrIo;
953 }
954
955 *link = (char*)data;
956 return Nfs3Ok;
957 }
958
959 static int
960 hfsextentkeycmp(uchar *buf, int len, int *order, Key *key)
961 {
962 Extentkey a, *b;
963 int diff;
964
965 if(getextentkey(&a, buf, len) < 0)
966 return -1;
967 b = key->priv;
968
969 diff = a.cnid - b->cnid;
970 if(diff == 0){
971 diff = a.type - b->type;
972 if(diff == 0)
973 diff = a.bno - b->bno;
974 }
975 *order = diff;
976 return 0;
977 }
978
979 static int
980 hfsextentsearch(Hfs *fs, u32int cnid, int type, u32int bno, u32int *startblock, Extent *e)
981 {
982 Extentkey k;
983 Key key;
984 Treeref ref;
985
986 key._cmp = hfsextentkeycmp;
987 key.priv = &k;
988 k.cnid = cnid;
989 k.type = type;
990 k.bno = bno;
991 if(hfstreesearch(&fs->extents, &key, nil, &ref) < 0)
992 goto notfound;
993 if(ref.dlen != NEXTENTS*Extentlen){
994 if(debug) fprint(2, "extents for fork %ud %d block %ud malformed (%d bytes)\n",
995 cnid, type, bno, ref.dlen);
996 goto notfound;
997 }
998 getextentkey(&k, ref.key, ref.klen);
999 if(k.cnid != cnid || k.type != type)
1000 goto notfound;
1001 if(startblock)
1002 *startblock = k.bno;
1003 getextents(e, ref.data);
1004 hfsrefput(&ref);
1005 return 0;
1006
1007 notfound:
1008 hfsrefput(&ref);
1009 return -1;
1010 }
1011
1012 static int
1013 hfscatalogkeycmp(uchar *buf, int len, int *order, Key *key)
1014 {
1015 return _hfscatalogkeycmp(buf, len, order, key, 1);
1016 }
1017
1018 static int
1019 hfscatalogikeycmp(uchar *buf, int len, int *order, Key *key)
1020 {
1021 return _hfscatalogkeycmp(buf, len, order, key, 0);
1022 }
1023
1024 static int
1025 hfscatsearch(Hfs *fs, Catalogkey *k, Treeref *ref)
1026 {
1027 Key key;
1028 int order;
1029
1030 key._cmp = fs->catalog.sensitive ? hfscatalogkeycmp : hfscatalogikeycmp;
1031 key.priv = k;
1032 if(hfstreesearch(&fs->catalog, &key, &order, ref) < 0 || order != 0){
1033 hfsrefput(ref);
1034 return -1;
1035 }
1036 return 0;
1037 }
1038
1039 static int
1040 _hfscatalogkeycmp(uchar *buf, int len, int *order, Key *key, int sensitive)
1041 {
1042 Catalogkey a, *b;
1043 int diff;
1044
1045 if(getcatalogkey(&a, buf, len, 0) < 0)
1046 return -1;
1047 b = key->priv;
1048
1049 diff = a.parent - b->parent;
1050 if(diff == 0){
1051 if(getname(&a.u.name, a.u.b) < 0)
1052 return -1;
1053 if(sensitive)
1054 diff = hfsnamecmp(&a.u.name, &b->u.name);
1055 else
1056 diff = hfsinamecmp(&a.u.name, &b->u.name);
1057 }
1058 *order = diff;
1059 return 0;
1060 }
1061
1062 static int
1063 hfskeycmp(uchar *k, int len, int *order, Key *key)
1064 {
1065 return (*key->_cmp)(k, len, order, key);
1066 }
1067
1068 /*
1069 Find the record with the largest key k' <= key.
1070 */
1071 static int
1072 hfstreesearch(Tree *tree, Key *key, int *porder, Treeref *ref)
1073 {
1074 u32int nno;
1075 int h, i, found, order, rel;
1076
1077 hfsref(tree, ref);
1078 nno = tree->root;
1079 rel = 0; /* silence a warning */
1080 for(h=tree->height; h>0; h--){
1081 if(hfsrefnode(ref, nno) < 0)
1082 goto error;
1083 found = -1;
1084 /*
1085 We could use binary search.
1086 */
1087 for(i=0; i < ref->node.nrec; i++){
1088 if(hfsrefrec(ref, i) < 0)
1089 goto error;
1090 if(hfskeycmp(ref->key, ref->klen, &order, key) < 0)
1091 goto error;
1092 if(order > 0)
1093 break;
1094 found = i;
1095 rel = order;
1096 if(order == 0)
1097 break;
1098 }
1099 if(found < 0 || hfsrefrec(ref, found) < 0)
1100 goto error;
1101 if(h == 1){
1102 if(porder)
1103 *porder = rel;
1104 return 0;
1105 }
1106 if(ref->dlen != 4){
1107 if(debug) fprint(2, "tree %ud node %ud rec %d bad %d-byte pointer\n",
1108 ref->cnid, ref->nno, ref->rno, ref->dlen);
1109 goto error;
1110 }
1111 nno = get32(ref->data);
1112 }
1113
1114 error:
1115 hfsrefput(ref);
1116 return -1;
1117 }
1118
1119 static void
1120 hfstreenodeclose(Block *b)
1121 {
1122 free(b);
1123 }
1124
1125 static Block*
1126 hfstreenode(Tree *tree, u32int nno)
1127 {
1128 Hfs *fs;
1129 Fork *fork;
1130 Block *b;
1131 int len;
1132
1133 fs = tree->fs;
1134 fork = tree->fork;
1135 len = tree->nodesize;
1136 if(nno >= tree->nnodes){
1137 if(debug) fprint(2, "bad tree %ud node %ud\n", tree->fork->cnid, nno);
1138 return nil;
1139 }
1140
1141 if(len == fs->blocksize)
1142 return hfsforkblock(fs, fork, nno);
1143
1144 b = mallocz(sizeof(Block)+len, 1);
1145 if(b == nil)
1146 return nil;
1147 b->data = (uchar*)&b[1];
1148 b->len = len;
1149 if(hfsforkread(fs, fork, b->data, len, (u64int)nno*len) < 0){
1150 free(b);
1151 return nil;
1152 }
1153 b->_close = hfstreenodeclose;
1154
1155 return b;
1156 }
1157
1158 /*
1159 After hfsref:
1160
1161 if rno >= 0, then every field is valid.
1162 if block != nil, then tree through node are valid.
1163 tree and cnid are valid.
1164 */
1165 static void
1166 hfsref(Tree *tree, Treeref *ref)
1167 {
1168 memset(ref, 0, sizeof(Treeref));
1169 ref->tree = tree;
1170 ref->cnid = ref->tree->fork->cnid;
1171 ref->rno = -1;
1172 }
1173
1174 static void
1175 hfsrefput(Treeref *ref)
1176 {
1177 blockput(ref->block);
1178 ref->block = nil;
1179 ref->rno = -1;
1180 }
1181
1182 static int
1183 hfsrefnode(Treeref *ref, u32int nno)
1184 {
1185 if(ref->block && ref->nno==nno)
1186 return 0;
1187
1188 ref->rno = -1;
1189 blockput(ref->block);
1190 if((ref->block = hfstreenode(ref->tree, nno)) == nil)
1191 return -1;
1192 ref->nno = nno;
1193 getnodedesc(&ref->node, ref->block->data);
1194 /*
1195 Hfsrefrec assumes all record offsets lie in the block.
1196 */
1197 if(ref->node.nrec > (ref->tree->nodesize-Ndlen-2)/2){
1198 if(debug) fprint(2, "tree %ud node %ud bad nrec %d\n",
1199 ref->cnid, ref->nno, ref->node.nrec);
1200 blockput(ref->block);
1201 ref->block = nil;
1202 return -1;
1203 }
1204 return 0;
1205 }
1206
1207 static int
1208 hfsrefrec(Treeref *ref, int rno)
1209 {
1210 uchar *node, *o, *r, *n;
1211 int klen;
1212
1213 if(ref->block == nil || rno < 0 || rno >= ref->node.nrec)
1214 return -1;
1215
1216 if(ref->rno == rno)
1217 return 0;
1218
1219 /*
1220 We could use Tree.indexkeylen to avoid reading offsets
1221 from extent tree nodes.
1222 */
1223 node = ref->block->data;
1224 o = node+ref->tree->nodesize-2*(rno+1);
1225 r = node+get16(o);
1226 n = node+get16(o-2);
1227 if(r < node+Ndlen || n <= r+2 || o < n){
1228 if(debug) fprint(2, "tree %ud node %ud rec %d bad offsets %d %d %d\n",
1229 ref->cnid, ref->nno, rno, r-node, n-node, o-node);
1230 return -1;
1231 }
1232 ref->rno = rno;
1233 klen = 2+get16(r); /* actual length */
1234 ref->klen = klen;
1235 ref->key = r;
1236 ref->data = r+klen+(klen&1);
1237 ref->dlen = n-ref->data; /* includes any pad byte */
1238 return 0;
1239 }
1240
1241 static int
1242 hfsrefnextrec(Treeref *ref)
1243 {
1244 int rno;
1245 u32int nno;
1246
1247 if(ref->block == nil)
1248 return -1;
1249 rno = ref->rno < 0 ? 0 : ref->rno+1;
1250 if(rno < ref->node.nrec)
1251 return hfsrefrec(ref, rno);
1252 nno = ref->node.next;
1253 if(nno==0 || hfsrefnode(ref, nno) < 0 || ref->node.nrec==0)
1254 return -1;
1255 return hfsrefrec(ref, 0);
1256 }
1257
1258 static int
1259 hfsforkread(Hfs *fs, Fork *fork, uchar *data, u32int count, u64int offset)
1260 {
1261 u32int bno;
1262 int skip, frag;
1263 Block *b;
1264
1265 if(offset+count > fork->size){
1266 if(debug) fprint(2, "read past end of fork\n");
1267 return -1;
1268 }
1269
1270 if(count == 0)
1271 return 0;
1272
1273 bno = offset/fs->blocksize;
1274 skip = offset%fs->blocksize;
1275 frag = fs->blocksize - skip;
1276 if(frag > count)
1277 frag = count;
1278 if((b = hfsforkblock(fs, fork, bno)) == nil)
1279 return -1;
1280 memmove(data, b->data+skip, frag);
1281 blockput(b);
1282 data += frag;
1283 count -= frag;
1284 bno++;
1285 while(count > fs->blocksize){
1286 if((b = hfsforkblock(fs, fork, bno)) == nil)
1287 return -1;
1288 memmove(data, b->data, fs->blocksize);
1289 blockput(b);
1290 data += fs->blocksize;
1291 count -= fs->blocksize;
1292 bno++;
1293 }
1294 if(count > 0){
1295 if((b = hfsforkblock(fs, fork, bno)) == nil)
1296 return -1;
1297 memmove(data, b->data, count);
1298 blockput(b);
1299 }
1300 return 0;
1301 }
1302
1303 static Block*
1304 hfsforkblock(Hfs *fs, Fork *fork, u32int bno)
1305 {
1306 u32int skip, start;
1307 int i;
1308 Extent *e;
1309 Extent other[NEXTENTS];
1310
1311 if(bno >= fork->nblocks){
1312 if(debug) fprint(2, "bad fork %ud %d block %ud\n",
1313 fork->cnid, fork->type, bno);
1314 return nil;
1315 }
1316 skip = bno;
1317 e = fork->extent;
1318 for(i=0; i<NEXTENTS; i++, e++){
1319 if(skip < e->count)
1320 return hfsblock(fs, e->start+skip);
1321 else
1322 skip -= e->count;
1323 }
1324 if(fork->cnid == ExtentsId){
1325 if(debug) fprint(2, "extents fork overflow\n");
1326 return nil;
1327 }
1328 if(hfsextentsearch(fs, fork->cnid, fork->type, bno, &start, other) < 0)
1329 return nil;
1330 skip = bno-start;
1331 e = other;
1332 for(i=0; i<NEXTENTS; i++, e++){
1333 if(skip < e->count)
1334 return hfsblock(fs, e->start+skip);
1335 else
1336 skip -= e->count;
1337 }
1338 if(debug) fprint(2, "bad extents overflow fork %ud %d block %ud skip %ud\n",
1339 fork->cnid, fork->type, bno, skip);
1340 return nil;
1341 }
1342
1343 static Block*
1344 hfsblock(Hfs *fs, u32int bno)
1345 {
1346 if(bno >= fs->nblock){
1347 if(debug) fprint(2, "bad block %ud\n", bno);
1348 return nil;
1349 }
1350 return diskread(fs->disk, fs->blocksize, (u64int)bno*fs->blocksize);
1351 }
1352
1353 static void
1354 getnodedesc(Node *n, uchar *b)
1355 {
1356 n->type = (s8int)b[8];
1357 n->next = get32(b);
1358 n->nrec = get16(b+10);
1359 }
1360
1361 static void
1362 getfork(Fork *f, u32int cnid, int type, uchar *b)
1363 {
1364 f->cnid = cnid;
1365 f->type = type;
1366 f->size = get64(b);
1367 f->nblocks = get32(b+12);
1368 getextents(f->extent, b+16);
1369 }
1370
1371 static void
1372 getextents(Extent *e, uchar *b)
1373 {
1374 int i;
1375
1376 for(i=0; i<NEXTENTS; i++){
1377 getextent(e+i, b);
1378 b += Extentlen;
1379 }
1380 }
1381
1382 static void
1383 getextent(Extent *e, uchar *b)
1384 {
1385 e->start = get32(b);
1386 e->count = get32(b+4);
1387 }
1388
1389 static int
1390 getextentkey(Extentkey *k, uchar *b, int len)
1391 {
1392 if(len != 12){
1393 if(debug) fprint(2, "bad extents key length %d\n", len);
1394 return -1;
1395 }
1396 k->cnid = get32(b+4);
1397 k->type = b[2];
1398 k->bno = get32(b+8);
1399 return 0;
1400 }
1401
1402 static int
1403 getcatalogrecord(Inode *ino, uchar *b, int blen)
1404 {
1405 int t;
1406 uchar *p;
1407
1408 if(blen != Folderlen && blen != Filelen){
1409 if(debug) fprint(2, "bad catalog entry length %d\n", blen);
1410 return -1;
1411 }
1412 t = get16(b);
1413 if((blen == Folderlen && t != Folder)
1414 || (blen == Filelen && t != File)){
1415 if(debug) fprint(2, "catalog entry type %d length %d mismatch\n", t, blen);
1416 return -1;
1417 }
1418 ino->cnid = get32(b+8);
1419 ino->fileid = ino->cnid;
1420 ino->mtime = gettime(b+16);
1421 ino->ctime = gettime(b+20);
1422 ino->atime = gettime(b+24);
1423 p = b+32;
1424 ino->nlink = 1;
1425 ino->uid = get32(p+0);
1426 ino->gid = get32(p+4);
1427 ino->mode = get16(p+10);
1428 ino->special = get32(p+12);
1429 if(t == Folder)
1430 ino->u.nentries = get32(b+4);
1431 else{
1432 getfork(&ino->u.f.dfork, ino->cnid, Dfork, b+88);
1433 getfork(&ino->u.f.rfork, ino->cnid, Rfork, b+168);
1434 memcpy(ino->u.f.info, b+48, Filen);
1435 ino->u.f.nhdr = 0;
1436 ino->u.f.fork = &ino->u.f.dfork;
1437 }
1438 return 0;
1439 }
1440
1441 static int
1442 getcatalogthread(Catalogkey *k, uchar *b, int blen)
1443 {
1444 int t;
1445
1446 if(blen > 10+2*NAMELEN){
1447 if(debug) fprint(2, "bad catalog thread length %d\n", blen);
1448 return -1;
1449 }
1450 t = get16(b);
1451 if(t != FolderThread && t != FileThread){
1452 if(debug) fprint(2, "bad catalog thread type %d\n", t);
1453 return -1;
1454 }
1455 return getcatalogkey(k, b+2, blen-2, 1);
1456 }
1457
1458 static int
1459 getcatalogkey(Catalogkey *k, uchar *b, int blen, int decode)
1460 {
1461 if(blen > 8+2*NAMELEN){
1462 if(debug) fprint(2, "bad catalog key length %d\n", blen);
1463 return -1;
1464 }
1465 k->parent = get32(b+2);
1466 if(decode)
1467 return getname(&k->u.name, b+6);
1468 k->u.b = b+6;
1469 return 0;
1470 }
1471
1472 static int
1473 getname(Name *n, uchar *b)
1474 {
1475 int i;
1476
1477 n->len = get16(b);
1478 if(n->len > NAMELEN){
1479 if(debug) fprint(2, "bad name length %d\n", n->len);
1480 return -1;
1481 }
1482 b += 2;
1483 for(i=0; i<n->len; i++, b += 2)
1484 n->name[i] = get16(b);
1485 return 0;
1486 }
1487
1488 static u32int
1489 gettime(uchar *b)
1490 {
1491 return get32(b) - 2082844800;
1492 }
1493
1494 static u64int
1495 get64(uchar *b)
1496 {
1497 return ((u64int)get32(b))<<32 | get32(b+4);
1498 }
1499
1500 static u32int
1501 get32(uchar *b)
1502 {
1503 return b[0]<<24 | b[1]<<16 | b[2]<<8 | b[3];
1504 }
1505
1506 static int
1507 get16(uchar *b)
1508 {
1509 return b[0]<<8 | b[1];
1510 }
1511
1512 static void
1513 put32(uchar *b, u32int n)
1514 {
1515 b[0] = n>>24;
1516 b[1] = n>>16;
1517 b[2] = n>>8;
1518 b[3] = n;
1519 }
1520
1521 /*
1522 Adapted from FastUnicodeCompare in Apple technical note 1150.
1523 */
1524 static u16int
1525 hfslcase[] =
1526 {
1527 /* High-byte indices ( == 0 iff no case mapping and no ignorables ) */
1528
1529 0x0100, 0x0200, 0x0000, 0x0300, 0x0400, 0x0500, 0x0000, 0x0000,
1530 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1531 0x0600, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1532 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1533 0x0700, 0x0800, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1534 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1535 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1536 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1537 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1538 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1539 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1540 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1541 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1542 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1543 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1544 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1545 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1546 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1547 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1548 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1549 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1550 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1551 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1552 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1553 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1554 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1555 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1556 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1557 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1558 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1559 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1560 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0900, 0x0A00,
1561
1562 /* Table 1 (for high byte 0x00) */
1563
1564 0xFFFF, 0x0001, 0x0002, 0x0003, 0x0004, 0x0005, 0x0006, 0x0007,
1565 0x0008, 0x0009, 0x000A, 0x000B, 0x000C, 0x000D, 0x000E, 0x000F,
1566 0x0010, 0x0011, 0x0012, 0x0013, 0x0014, 0x0015, 0x0016, 0x0017,
1567 0x0018, 0x0019, 0x001A, 0x001B, 0x001C, 0x001D, 0x001E, 0x001F,
1568 0x0020, 0x0021, 0x0022, 0x0023, 0x0024, 0x0025, 0x0026, 0x0027,
1569 0x0028, 0x0029, 0x002A, 0x002B, 0x002C, 0x002D, 0x002E, 0x002F,
1570 0x0030, 0x0031, 0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037,
1571 0x0038, 0x0039, 0x003A, 0x003B, 0x003C, 0x003D, 0x003E, 0x003F,
1572 0x0040, 0x0061, 0x0062, 0x0063, 0x0064, 0x0065, 0x0066, 0x0067,
1573 0x0068, 0x0069, 0x006A, 0x006B, 0x006C, 0x006D, 0x006E, 0x006F,
1574 0x0070, 0x0071, 0x0072, 0x0073, 0x0074, 0x0075, 0x0076, 0x0077,
1575 0x0078, 0x0079, 0x007A, 0x005B, 0x005C, 0x005D, 0x005E, 0x005F,
1576 0x0060, 0x0061, 0x0062, 0x0063, 0x0064, 0x0065, 0x0066, 0x0067,
1577 0x0068, 0x0069, 0x006A, 0x006B, 0x006C, 0x006D, 0x006E, 0x006F,
1578 0x0070, 0x0071, 0x0072, 0x0073, 0x0074, 0x0075, 0x0076, 0x0077,
1579 0x0078, 0x0079, 0x007A, 0x007B, 0x007C, 0x007D, 0x007E, 0x007F,
1580 0x0080, 0x0081, 0x0082, 0x0083, 0x0084, 0x0085, 0x0086, 0x0087,
1581 0x0088, 0x0089, 0x008A, 0x008B, 0x008C, 0x008D, 0x008E, 0x008F,
1582 0x0090, 0x0091, 0x0092, 0x0093, 0x0094, 0x0095, 0x0096, 0x0097,
1583 0x0098, 0x0099, 0x009A, 0x009B, 0x009C, 0x009D, 0x009E, 0x009F,
1584 0x00A0, 0x00A1, 0x00A2, 0x00A3, 0x00A4, 0x00A5, 0x00A6, 0x00A7,
1585 0x00A8, 0x00A9, 0x00AA, 0x00AB, 0x00AC, 0x00AD, 0x00AE, 0x00AF,
1586 0x00B0, 0x00B1, 0x00B2, 0x00B3, 0x00B4, 0x00B5, 0x00B6, 0x00B7,
1587 0x00B8, 0x00B9, 0x00BA, 0x00BB, 0x00BC, 0x00BD, 0x00BE, 0x00BF,
1588 0x00C0, 0x00C1, 0x00C2, 0x00C3, 0x00C4, 0x00C5, 0x00E6, 0x00C7,
1589 0x00C8, 0x00C9, 0x00CA, 0x00CB, 0x00CC, 0x00CD, 0x00CE, 0x00CF,
1590 0x00F0, 0x00D1, 0x00D2, 0x00D3, 0x00D4, 0x00D5, 0x00D6, 0x00D7,
1591 0x00F8, 0x00D9, 0x00DA, 0x00DB, 0x00DC, 0x00DD, 0x00FE, 0x00DF,
1592 0x00E0, 0x00E1, 0x00E2, 0x00E3, 0x00E4, 0x00E5, 0x00E6, 0x00E7,
1593 0x00E8, 0x00E9, 0x00EA, 0x00EB, 0x00EC, 0x00ED, 0x00EE, 0x00EF,
1594 0x00F0, 0x00F1, 0x00F2, 0x00F3, 0x00F4, 0x00F5, 0x00F6, 0x00F7,
1595 0x00F8, 0x00F9, 0x00FA, 0x00FB, 0x00FC, 0x00FD, 0x00FE, 0x00FF,
1596
1597 /* Table 2 (for high byte 0x01) */
1598
1599 0x0100, 0x0101, 0x0102, 0x0103, 0x0104, 0x0105, 0x0106, 0x0107,
1600 0x0108, 0x0109, 0x010A, 0x010B, 0x010C, 0x010D, 0x010E, 0x010F,
1601 0x0111, 0x0111, 0x0112, 0x0113, 0x0114, 0x0115, 0x0116, 0x0117,
1602 0x0118, 0x0119, 0x011A, 0x011B, 0x011C, 0x011D, 0x011E, 0x011F,
1603 0x0120, 0x0121, 0x0122, 0x0123, 0x0124, 0x0125, 0x0127, 0x0127,
1604 0x0128, 0x0129, 0x012A, 0x012B, 0x012C, 0x012D, 0x012E, 0x012F,
1605 0x0130, 0x0131, 0x0133, 0x0133, 0x0134, 0x0135, 0x0136, 0x0137,
1606 0x0138, 0x0139, 0x013A, 0x013B, 0x013C, 0x013D, 0x013E, 0x0140,
1607 0x0140, 0x0142, 0x0142, 0x0143, 0x0144, 0x0145, 0x0146, 0x0147,
1608 0x0148, 0x0149, 0x014B, 0x014B, 0x014C, 0x014D, 0x014E, 0x014F,
1609 0x0150, 0x0151, 0x0153, 0x0153, 0x0154, 0x0155, 0x0156, 0x0157,
1610 0x0158, 0x0159, 0x015A, 0x015B, 0x015C, 0x015D, 0x015E, 0x015F,
1611 0x0160, 0x0161, 0x0162, 0x0163, 0x0164, 0x0165, 0x0167, 0x0167,
1612 0x0168, 0x0169, 0x016A, 0x016B, 0x016C, 0x016D, 0x016E, 0x016F,
1613 0x0170, 0x0171, 0x0172, 0x0173, 0x0174, 0x0175, 0x0176, 0x0177,
1614 0x0178, 0x0179, 0x017A, 0x017B, 0x017C, 0x017D, 0x017E, 0x017F,
1615 0x0180, 0x0253, 0x0183, 0x0183, 0x0185, 0x0185, 0x0254, 0x0188,
1616 0x0188, 0x0256, 0x0257, 0x018C, 0x018C, 0x018D, 0x01DD, 0x0259,
1617 0x025B, 0x0192, 0x0192, 0x0260, 0x0263, 0x0195, 0x0269, 0x0268,
1618 0x0199, 0x0199, 0x019A, 0x019B, 0x026F, 0x0272, 0x019E, 0x0275,
1619 0x01A0, 0x01A1, 0x01A3, 0x01A3, 0x01A5, 0x01A5, 0x01A6, 0x01A8,
1620 0x01A8, 0x0283, 0x01AA, 0x01AB, 0x01AD, 0x01AD, 0x0288, 0x01AF,
1621 0x01B0, 0x028A, 0x028B, 0x01B4, 0x01B4, 0x01B6, 0x01B6, 0x0292,
1622 0x01B9, 0x01B9, 0x01BA, 0x01BB, 0x01BD, 0x01BD, 0x01BE, 0x01BF,
1623 0x01C0, 0x01C1, 0x01C2, 0x01C3, 0x01C6, 0x01C6, 0x01C6, 0x01C9,
1624 0x01C9, 0x01C9, 0x01CC, 0x01CC, 0x01CC, 0x01CD, 0x01CE, 0x01CF,
1625 0x01D0, 0x01D1, 0x01D2, 0x01D3, 0x01D4, 0x01D5, 0x01D6, 0x01D7,
1626 0x01D8, 0x01D9, 0x01DA, 0x01DB, 0x01DC, 0x01DD, 0x01DE, 0x01DF,
1627 0x01E0, 0x01E1, 0x01E2, 0x01E3, 0x01E5, 0x01E5, 0x01E6, 0x01E7,
1628 0x01E8, 0x01E9, 0x01EA, 0x01EB, 0x01EC, 0x01ED, 0x01EE, 0x01EF,
1629 0x01F0, 0x01F3, 0x01F3, 0x01F3, 0x01F4, 0x01F5, 0x01F6, 0x01F7,
1630 0x01F8, 0x01F9, 0x01FA, 0x01FB, 0x01FC, 0x01FD, 0x01FE, 0x01FF,
1631
1632 /* Table 3 (for high byte 0x03) */
1633
1634 0x0300, 0x0301, 0x0302, 0x0303, 0x0304, 0x0305, 0x0306, 0x0307,
1635 0x0308, 0x0309, 0x030A, 0x030B, 0x030C, 0x030D, 0x030E, 0x030F,
1636 0x0310, 0x0311, 0x0312, 0x0313, 0x0314, 0x0315, 0x0316, 0x0317,
1637 0x0318, 0x0319, 0x031A, 0x031B, 0x031C, 0x031D, 0x031E, 0x031F,
1638 0x0320, 0x0321, 0x0322, 0x0323, 0x0324, 0x0325, 0x0326, 0x0327,
1639 0x0328, 0x0329, 0x032A, 0x032B, 0x032C, 0x032D, 0x032E, 0x032F,
1640 0x0330, 0x0331, 0x0332, 0x0333, 0x0334, 0x0335, 0x0336, 0x0337,
1641 0x0338, 0x0339, 0x033A, 0x033B, 0x033C, 0x033D, 0x033E, 0x033F,
1642 0x0340, 0x0341, 0x0342, 0x0343, 0x0344, 0x0345, 0x0346, 0x0347,
1643 0x0348, 0x0349, 0x034A, 0x034B, 0x034C, 0x034D, 0x034E, 0x034F,
1644 0x0350, 0x0351, 0x0352, 0x0353, 0x0354, 0x0355, 0x0356, 0x0357,
1645 0x0358, 0x0359, 0x035A, 0x035B, 0x035C, 0x035D, 0x035E, 0x035F,
1646 0x0360, 0x0361, 0x0362, 0x0363, 0x0364, 0x0365, 0x0366, 0x0367,
1647 0x0368, 0x0369, 0x036A, 0x036B, 0x036C, 0x036D, 0x036E, 0x036F,
1648 0x0370, 0x0371, 0x0372, 0x0373, 0x0374, 0x0375, 0x0376, 0x0377,
1649 0x0378, 0x0379, 0x037A, 0x037B, 0x037C, 0x037D, 0x037E, 0x037F,
1650 0x0380, 0x0381, 0x0382, 0x0383, 0x0384, 0x0385, 0x0386, 0x0387,
1651 0x0388, 0x0389, 0x038A, 0x038B, 0x038C, 0x038D, 0x038E, 0x038F,
1652 0x0390, 0x03B1, 0x03B2, 0x03B3, 0x03B4, 0x03B5, 0x03B6, 0x03B7,
1653 0x03B8, 0x03B9, 0x03BA, 0x03BB, 0x03BC, 0x03BD, 0x03BE, 0x03BF,
1654 0x03C0, 0x03C1, 0x03A2, 0x03C3, 0x03C4, 0x03C5, 0x03C6, 0x03C7,
1655 0x03C8, 0x03C9, 0x03AA, 0x03AB, 0x03AC, 0x03AD, 0x03AE, 0x03AF,
1656 0x03B0, 0x03B1, 0x03B2, 0x03B3, 0x03B4, 0x03B5, 0x03B6, 0x03B7,
1657 0x03B8, 0x03B9, 0x03BA, 0x03BB, 0x03BC, 0x03BD, 0x03BE, 0x03BF,
1658 0x03C0, 0x03C1, 0x03C2, 0x03C3, 0x03C4, 0x03C5, 0x03C6, 0x03C7,
1659 0x03C8, 0x03C9, 0x03CA, 0x03CB, 0x03CC, 0x03CD, 0x03CE, 0x03CF,
1660 0x03D0, 0x03D1, 0x03D2, 0x03D3, 0x03D4, 0x03D5, 0x03D6, 0x03D7,
1661 0x03D8, 0x03D9, 0x03DA, 0x03DB, 0x03DC, 0x03DD, 0x03DE, 0x03DF,
1662 0x03E0, 0x03E1, 0x03E3, 0x03E3, 0x03E5, 0x03E5, 0x03E7, 0x03E7,
1663 0x03E9, 0x03E9, 0x03EB, 0x03EB, 0x03ED, 0x03ED, 0x03EF, 0x03EF,
1664 0x03F0, 0x03F1, 0x03F2, 0x03F3, 0x03F4, 0x03F5, 0x03F6, 0x03F7,
1665 0x03F8, 0x03F9, 0x03FA, 0x03FB, 0x03FC, 0x03FD, 0x03FE, 0x03FF,
1666
1667 /* Table 4 (for high byte 0x04) */
1668
1669 0x0400, 0x0401, 0x0452, 0x0403, 0x0454, 0x0455, 0x0456, 0x0407,
1670 0x0458, 0x0459, 0x045A, 0x045B, 0x040C, 0x040D, 0x040E, 0x045F,
1671 0x0430, 0x0431, 0x0432, 0x0433, 0x0434, 0x0435, 0x0436, 0x0437,
1672 0x0438, 0x0419, 0x043A, 0x043B, 0x043C, 0x043D, 0x043E, 0x043F,
1673 0x0440, 0x0441, 0x0442, 0x0443, 0x0444, 0x0445, 0x0446, 0x0447,
1674 0x0448, 0x0449, 0x044A, 0x044B, 0x044C, 0x044D, 0x044E, 0x044F,
1675 0x0430, 0x0431, 0x0432, 0x0433, 0x0434, 0x0435, 0x0436, 0x0437,
1676 0x0438, 0x0439, 0x043A, 0x043B, 0x043C, 0x043D, 0x043E, 0x043F,
1677 0x0440, 0x0441, 0x0442, 0x0443, 0x0444, 0x0445, 0x0446, 0x0447,
1678 0x0448, 0x0449, 0x044A, 0x044B, 0x044C, 0x044D, 0x044E, 0x044F,
1679 0x0450, 0x0451, 0x0452, 0x0453, 0x0454, 0x0455, 0x0456, 0x0457,
1680 0x0458, 0x0459, 0x045A, 0x045B, 0x045C, 0x045D, 0x045E, 0x045F,
1681 0x0461, 0x0461, 0x0463, 0x0463, 0x0465, 0x0465, 0x0467, 0x0467,
1682 0x0469, 0x0469, 0x046B, 0x046B, 0x046D, 0x046D, 0x046F, 0x046F,
1683 0x0471, 0x0471, 0x0473, 0x0473, 0x0475, 0x0475, 0x0476, 0x0477,
1684 0x0479, 0x0479, 0x047B, 0x047B, 0x047D, 0x047D, 0x047F, 0x047F,
1685 0x0481, 0x0481, 0x0482, 0x0483, 0x0484, 0x0485, 0x0486, 0x0487,
1686 0x0488, 0x0489, 0x048A, 0x048B, 0x048C, 0x048D, 0x048E, 0x048F,
1687 0x0491, 0x0491, 0x0493, 0x0493, 0x0495, 0x0495, 0x0497, 0x0497,
1688 0x0499, 0x0499, 0x049B, 0x049B, 0x049D, 0x049D, 0x049F, 0x049F,
1689 0x04A1, 0x04A1, 0x04A3, 0x04A3, 0x04A5, 0x04A5, 0x04A7, 0x04A7,
1690 0x04A9, 0x04A9, 0x04AB, 0x04AB, 0x04AD, 0x04AD, 0x04AF, 0x04AF,
1691 0x04B1, 0x04B1, 0x04B3, 0x04B3, 0x04B5, 0x04B5, 0x04B7, 0x04B7,
1692 0x04B9, 0x04B9, 0x04BB, 0x04BB, 0x04BD, 0x04BD, 0x04BF, 0x04BF,
1693 0x04C0, 0x04C1, 0x04C2, 0x04C4, 0x04C4, 0x04C5, 0x04C6, 0x04C8,
1694 0x04C8, 0x04C9, 0x04CA, 0x04CC, 0x04CC, 0x04CD, 0x04CE, 0x04CF,
1695 0x04D0, 0x04D1, 0x04D2, 0x04D3, 0x04D4, 0x04D5, 0x04D6, 0x04D7,
1696 0x04D8, 0x04D9, 0x04DA, 0x04DB, 0x04DC, 0x04DD, 0x04DE, 0x04DF,
1697 0x04E0, 0x04E1, 0x04E2, 0x04E3, 0x04E4, 0x04E5, 0x04E6, 0x04E7,
1698 0x04E8, 0x04E9, 0x04EA, 0x04EB, 0x04EC, 0x04ED, 0x04EE, 0x04EF,
1699 0x04F0, 0x04F1, 0x04F2, 0x04F3, 0x04F4, 0x04F5, 0x04F6, 0x04F7,
1700 0x04F8, 0x04F9, 0x04FA, 0x04FB, 0x04FC, 0x04FD, 0x04FE, 0x04FF,
1701
1702 /* Table 5 (for high byte 0x05) */
1703
1704 0x0500, 0x0501, 0x0502, 0x0503, 0x0504, 0x0505, 0x0506, 0x0507,
1705 0x0508, 0x0509, 0x050A, 0x050B, 0x050C, 0x050D, 0x050E, 0x050F,
1706 0x0510, 0x0511, 0x0512, 0x0513, 0x0514, 0x0515, 0x0516, 0x0517,
1707 0x0518, 0x0519, 0x051A, 0x051B, 0x051C, 0x051D, 0x051E, 0x051F,
1708 0x0520, 0x0521, 0x0522, 0x0523, 0x0524, 0x0525, 0x0526, 0x0527,
1709 0x0528, 0x0529, 0x052A, 0x052B, 0x052C, 0x052D, 0x052E, 0x052F,
1710 0x0530, 0x0561, 0x0562, 0x0563, 0x0564, 0x0565, 0x0566, 0x0567,
1711 0x0568, 0x0569, 0x056A, 0x056B, 0x056C, 0x056D, 0x056E, 0x056F,
1712 0x0570, 0x0571, 0x0572, 0x0573, 0x0574, 0x0575, 0x0576, 0x0577,
1713 0x0578, 0x0579, 0x057A, 0x057B, 0x057C, 0x057D, 0x057E, 0x057F,
1714 0x0580, 0x0581, 0x0582, 0x0583, 0x0584, 0x0585, 0x0586, 0x0557,
1715 0x0558, 0x0559, 0x055A, 0x055B, 0x055C, 0x055D, 0x055E, 0x055F,
1716 0x0560, 0x0561, 0x0562, 0x0563, 0x0564, 0x0565, 0x0566, 0x0567,
1717 0x0568, 0x0569, 0x056A, 0x056B, 0x056C, 0x056D, 0x056E, 0x056F,
1718 0x0570, 0x0571, 0x0572, 0x0573, 0x0574, 0x0575, 0x0576, 0x0577,
1719 0x0578, 0x0579, 0x057A, 0x057B, 0x057C, 0x057D, 0x057E, 0x057F,
1720 0x0580, 0x0581, 0x0582, 0x0583, 0x0584, 0x0585, 0x0586, 0x0587,
1721 0x0588, 0x0589, 0x058A, 0x058B, 0x058C, 0x058D, 0x058E, 0x058F,
1722 0x0590, 0x0591, 0x0592, 0x0593, 0x0594, 0x0595, 0x0596, 0x0597,
1723 0x0598, 0x0599, 0x059A, 0x059B, 0x059C, 0x059D, 0x059E, 0x059F,
1724 0x05A0, 0x05A1, 0x05A2, 0x05A3, 0x05A4, 0x05A5, 0x05A6, 0x05A7,
1725 0x05A8, 0x05A9, 0x05AA, 0x05AB, 0x05AC, 0x05AD, 0x05AE, 0x05AF,
1726 0x05B0, 0x05B1, 0x05B2, 0x05B3, 0x05B4, 0x05B5, 0x05B6, 0x05B7,
1727 0x05B8, 0x05B9, 0x05BA, 0x05BB, 0x05BC, 0x05BD, 0x05BE, 0x05BF,
1728 0x05C0, 0x05C1, 0x05C2, 0x05C3, 0x05C4, 0x05C5, 0x05C6, 0x05C7,
1729 0x05C8, 0x05C9, 0x05CA, 0x05CB, 0x05CC, 0x05CD, 0x05CE, 0x05CF,
1730 0x05D0, 0x05D1, 0x05D2, 0x05D3, 0x05D4, 0x05D5, 0x05D6, 0x05D7,
1731 0x05D8, 0x05D9, 0x05DA, 0x05DB, 0x05DC, 0x05DD, 0x05DE, 0x05DF,
1732 0x05E0, 0x05E1, 0x05E2, 0x05E3, 0x05E4, 0x05E5, 0x05E6, 0x05E7,
1733 0x05E8, 0x05E9, 0x05EA, 0x05EB, 0x05EC, 0x05ED, 0x05EE, 0x05EF,
1734 0x05F0, 0x05F1, 0x05F2, 0x05F3, 0x05F4, 0x05F5, 0x05F6, 0x05F7,
1735 0x05F8, 0x05F9, 0x05FA, 0x05FB, 0x05FC, 0x05FD, 0x05FE, 0x05FF,
1736
1737 /* Table 6 (for high byte 0x10) */
1738
1739 0x1000, 0x1001, 0x1002, 0x1003, 0x1004, 0x1005, 0x1006, 0x1007,
1740 0x1008, 0x1009, 0x100A, 0x100B, 0x100C, 0x100D, 0x100E, 0x100F,
1741 0x1010, 0x1011, 0x1012, 0x1013, 0x1014, 0x1015, 0x1016, 0x1017,
1742 0x1018, 0x1019, 0x101A, 0x101B, 0x101C, 0x101D, 0x101E, 0x101F,
1743 0x1020, 0x1021, 0x1022, 0x1023, 0x1024, 0x1025, 0x1026, 0x1027,
1744 0x1028, 0x1029, 0x102A, 0x102B, 0x102C, 0x102D, 0x102E, 0x102F,
1745 0x1030, 0x1031, 0x1032, 0x1033, 0x1034, 0x1035, 0x1036, 0x1037,
1746 0x1038, 0x1039, 0x103A, 0x103B, 0x103C, 0x103D, 0x103E, 0x103F,
1747 0x1040, 0x1041, 0x1042, 0x1043, 0x1044, 0x1045, 0x1046, 0x1047,
1748 0x1048, 0x1049, 0x104A, 0x104B, 0x104C, 0x104D, 0x104E, 0x104F,
1749 0x1050, 0x1051, 0x1052, 0x1053, 0x1054, 0x1055, 0x1056, 0x1057,
1750 0x1058, 0x1059, 0x105A, 0x105B, 0x105C, 0x105D, 0x105E, 0x105F,
1751 0x1060, 0x1061, 0x1062, 0x1063, 0x1064, 0x1065, 0x1066, 0x1067,
1752 0x1068, 0x1069, 0x106A, 0x106B, 0x106C, 0x106D, 0x106E, 0x106F,
1753 0x1070, 0x1071, 0x1072, 0x1073, 0x1074, 0x1075, 0x1076, 0x1077,
1754 0x1078, 0x1079, 0x107A, 0x107B, 0x107C, 0x107D, 0x107E, 0x107F,
1755 0x1080, 0x1081, 0x1082, 0x1083, 0x1084, 0x1085, 0x1086, 0x1087,
1756 0x1088, 0x1089, 0x108A, 0x108B, 0x108C, 0x108D, 0x108E, 0x108F,
1757 0x1090, 0x1091, 0x1092, 0x1093, 0x1094, 0x1095, 0x1096, 0x1097,
1758 0x1098, 0x1099, 0x109A, 0x109B, 0x109C, 0x109D, 0x109E, 0x109F,
1759 0x10D0, 0x10D1, 0x10D2, 0x10D3, 0x10D4, 0x10D5, 0x10D6, 0x10D7,
1760 0x10D8, 0x10D9, 0x10DA, 0x10DB, 0x10DC, 0x10DD, 0x10DE, 0x10DF,
1761 0x10E0, 0x10E1, 0x10E2, 0x10E3, 0x10E4, 0x10E5, 0x10E6, 0x10E7,
1762 0x10E8, 0x10E9, 0x10EA, 0x10EB, 0x10EC, 0x10ED, 0x10EE, 0x10EF,
1763 0x10F0, 0x10F1, 0x10F2, 0x10F3, 0x10F4, 0x10F5, 0x10C6, 0x10C7,
1764 0x10C8, 0x10C9, 0x10CA, 0x10CB, 0x10CC, 0x10CD, 0x10CE, 0x10CF,
1765 0x10D0, 0x10D1, 0x10D2, 0x10D3, 0x10D4, 0x10D5, 0x10D6, 0x10D7,
1766 0x10D8, 0x10D9, 0x10DA, 0x10DB, 0x10DC, 0x10DD, 0x10DE, 0x10DF,
1767 0x10E0, 0x10E1, 0x10E2, 0x10E3, 0x10E4, 0x10E5, 0x10E6, 0x10E7,
1768 0x10E8, 0x10E9, 0x10EA, 0x10EB, 0x10EC, 0x10ED, 0x10EE, 0x10EF,
1769 0x10F0, 0x10F1, 0x10F2, 0x10F3, 0x10F4, 0x10F5, 0x10F6, 0x10F7,
1770 0x10F8, 0x10F9, 0x10FA, 0x10FB, 0x10FC, 0x10FD, 0x10FE, 0x10FF,
1771
1772 /* Table 7 (for high byte 0x20) */
1773
1774 0x2000, 0x2001, 0x2002, 0x2003, 0x2004, 0x2005, 0x2006, 0x2007,
1775 0x2008, 0x2009, 0x200A, 0x200B, 0x0000, 0x0000, 0x0000, 0x0000,
1776 0x2010, 0x2011, 0x2012, 0x2013, 0x2014, 0x2015, 0x2016, 0x2017,
1777 0x2018, 0x2019, 0x201A, 0x201B, 0x201C, 0x201D, 0x201E, 0x201F,
1778 0x2020, 0x2021, 0x2022, 0x2023, 0x2024, 0x2025, 0x2026, 0x2027,
1779 0x2028, 0x2029, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x202F,
1780 0x2030, 0x2031, 0x2032, 0x2033, 0x2034, 0x2035, 0x2036, 0x2037,
1781 0x2038, 0x2039, 0x203A, 0x203B, 0x203C, 0x203D, 0x203E, 0x203F,
1782 0x2040, 0x2041, 0x2042, 0x2043, 0x2044, 0x2045, 0x2046, 0x2047,
1783 0x2048, 0x2049, 0x204A, 0x204B, 0x204C, 0x204D, 0x204E, 0x204F,
1784 0x2050, 0x2051, 0x2052, 0x2053, 0x2054, 0x2055, 0x2056, 0x2057,
1785 0x2058, 0x2059, 0x205A, 0x205B, 0x205C, 0x205D, 0x205E, 0x205F,
1786 0x2060, 0x2061, 0x2062, 0x2063, 0x2064, 0x2065, 0x2066, 0x2067,
1787 0x2068, 0x2069, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1788 0x2070, 0x2071, 0x2072, 0x2073, 0x2074, 0x2075, 0x2076, 0x2077,
1789 0x2078, 0x2079, 0x207A, 0x207B, 0x207C, 0x207D, 0x207E, 0x207F,
1790 0x2080, 0x2081, 0x2082, 0x2083, 0x2084, 0x2085, 0x2086, 0x2087,
1791 0x2088, 0x2089, 0x208A, 0x208B, 0x208C, 0x208D, 0x208E, 0x208F,
1792 0x2090, 0x2091, 0x2092, 0x2093, 0x2094, 0x2095, 0x2096, 0x2097,
1793 0x2098, 0x2099, 0x209A, 0x209B, 0x209C, 0x209D, 0x209E, 0x209F,
1794 0x20A0, 0x20A1, 0x20A2, 0x20A3, 0x20A4, 0x20A5, 0x20A6, 0x20A7,
1795 0x20A8, 0x20A9, 0x20AA, 0x20AB, 0x20AC, 0x20AD, 0x20AE, 0x20AF,
1796 0x20B0, 0x20B1, 0x20B2, 0x20B3, 0x20B4, 0x20B5, 0x20B6, 0x20B7,
1797 0x20B8, 0x20B9, 0x20BA, 0x20BB, 0x20BC, 0x20BD, 0x20BE, 0x20BF,
1798 0x20C0, 0x20C1, 0x20C2, 0x20C3, 0x20C4, 0x20C5, 0x20C6, 0x20C7,
1799 0x20C8, 0x20C9, 0x20CA, 0x20CB, 0x20CC, 0x20CD, 0x20CE, 0x20CF,
1800 0x20D0, 0x20D1, 0x20D2, 0x20D3, 0x20D4, 0x20D5, 0x20D6, 0x20D7,
1801 0x20D8, 0x20D9, 0x20DA, 0x20DB, 0x20DC, 0x20DD, 0x20DE, 0x20DF,
1802 0x20E0, 0x20E1, 0x20E2, 0x20E3, 0x20E4, 0x20E5, 0x20E6, 0x20E7,
1803 0x20E8, 0x20E9, 0x20EA, 0x20EB, 0x20EC, 0x20ED, 0x20EE, 0x20EF,
1804 0x20F0, 0x20F1, 0x20F2, 0x20F3, 0x20F4, 0x20F5, 0x20F6, 0x20F7,
1805 0x20F8, 0x20F9, 0x20FA, 0x20FB, 0x20FC, 0x20FD, 0x20FE, 0x20FF,
1806
1807 /* Table 8 (for high byte 0x21) */
1808
1809 0x2100, 0x2101, 0x2102, 0x2103, 0x2104, 0x2105, 0x2106, 0x2107,
1810 0x2108, 0x2109, 0x210A, 0x210B, 0x210C, 0x210D, 0x210E, 0x210F,
1811 0x2110, 0x2111, 0x2112, 0x2113, 0x2114, 0x2115, 0x2116, 0x2117,
1812 0x2118, 0x2119, 0x211A, 0x211B, 0x211C, 0x211D, 0x211E, 0x211F,
1813 0x2120, 0x2121, 0x2122, 0x2123, 0x2124, 0x2125, 0x2126, 0x2127,
1814 0x2128, 0x2129, 0x212A, 0x212B, 0x212C, 0x212D, 0x212E, 0x212F,
1815 0x2130, 0x2131, 0x2132, 0x2133, 0x2134, 0x2135, 0x2136, 0x2137,
1816 0x2138, 0x2139, 0x213A, 0x213B, 0x213C, 0x213D, 0x213E, 0x213F,
1817 0x2140, 0x2141, 0x2142, 0x2143, 0x2144, 0x2145, 0x2146, 0x2147,
1818 0x2148, 0x2149, 0x214A, 0x214B, 0x214C, 0x214D, 0x214E, 0x214F,
1819 0x2150, 0x2151, 0x2152, 0x2153, 0x2154, 0x2155, 0x2156, 0x2157,
1820 0x2158, 0x2159, 0x215A, 0x215B, 0x215C, 0x215D, 0x215E, 0x215F,
1821 0x2170, 0x2171, 0x2172, 0x2173, 0x2174, 0x2175, 0x2176, 0x2177,
1822 0x2178, 0x2179, 0x217A, 0x217B, 0x217C, 0x217D, 0x217E, 0x217F,
1823 0x2170, 0x2171, 0x2172, 0x2173, 0x2174, 0x2175, 0x2176, 0x2177,
1824 0x2178, 0x2179, 0x217A, 0x217B, 0x217C, 0x217D, 0x217E, 0x217F,
1825 0x2180, 0x2181, 0x2182, 0x2183, 0x2184, 0x2185, 0x2186, 0x2187,
1826 0x2188, 0x2189, 0x218A, 0x218B, 0x218C, 0x218D, 0x218E, 0x218F,
1827 0x2190, 0x2191, 0x2192, 0x2193, 0x2194, 0x2195, 0x2196, 0x2197,
1828 0x2198, 0x2199, 0x219A, 0x219B, 0x219C, 0x219D, 0x219E, 0x219F,
1829 0x21A0, 0x21A1, 0x21A2, 0x21A3, 0x21A4, 0x21A5, 0x21A6, 0x21A7,
1830 0x21A8, 0x21A9, 0x21AA, 0x21AB, 0x21AC, 0x21AD, 0x21AE, 0x21AF,
1831 0x21B0, 0x21B1, 0x21B2, 0x21B3, 0x21B4, 0x21B5, 0x21B6, 0x21B7,
1832 0x21B8, 0x21B9, 0x21BA, 0x21BB, 0x21BC, 0x21BD, 0x21BE, 0x21BF,
1833 0x21C0, 0x21C1, 0x21C2, 0x21C3, 0x21C4, 0x21C5, 0x21C6, 0x21C7,
1834 0x21C8, 0x21C9, 0x21CA, 0x21CB, 0x21CC, 0x21CD, 0x21CE, 0x21CF,
1835 0x21D0, 0x21D1, 0x21D2, 0x21D3, 0x21D4, 0x21D5, 0x21D6, 0x21D7,
1836 0x21D8, 0x21D9, 0x21DA, 0x21DB, 0x21DC, 0x21DD, 0x21DE, 0x21DF,
1837 0x21E0, 0x21E1, 0x21E2, 0x21E3, 0x21E4, 0x21E5, 0x21E6, 0x21E7,
1838 0x21E8, 0x21E9, 0x21EA, 0x21EB, 0x21EC, 0x21ED, 0x21EE, 0x21EF,
1839 0x21F0, 0x21F1, 0x21F2, 0x21F3, 0x21F4, 0x21F5, 0x21F6, 0x21F7,
1840 0x21F8, 0x21F9, 0x21FA, 0x21FB, 0x21FC, 0x21FD, 0x21FE, 0x21FF,
1841
1842 /* Table 9 (for high byte 0xFE) */
1843
1844 0xFE00, 0xFE01, 0xFE02, 0xFE03, 0xFE04, 0xFE05, 0xFE06, 0xFE07,
1845 0xFE08, 0xFE09, 0xFE0A, 0xFE0B, 0xFE0C, 0xFE0D, 0xFE0E, 0xFE0F,
1846 0xFE10, 0xFE11, 0xFE12, 0xFE13, 0xFE14, 0xFE15, 0xFE16, 0xFE17,
1847 0xFE18, 0xFE19, 0xFE1A, 0xFE1B, 0xFE1C, 0xFE1D, 0xFE1E, 0xFE1F,
1848 0xFE20, 0xFE21, 0xFE22, 0xFE23, 0xFE24, 0xFE25, 0xFE26, 0xFE27,
1849 0xFE28, 0xFE29, 0xFE2A, 0xFE2B, 0xFE2C, 0xFE2D, 0xFE2E, 0xFE2F,
1850 0xFE30, 0xFE31, 0xFE32, 0xFE33, 0xFE34, 0xFE35, 0xFE36, 0xFE37,
1851 0xFE38, 0xFE39, 0xFE3A, 0xFE3B, 0xFE3C, 0xFE3D, 0xFE3E, 0xFE3F,
1852 0xFE40, 0xFE41, 0xFE42, 0xFE43, 0xFE44, 0xFE45, 0xFE46, 0xFE47,
1853 0xFE48, 0xFE49, 0xFE4A, 0xFE4B, 0xFE4C, 0xFE4D, 0xFE4E, 0xFE4F,
1854 0xFE50, 0xFE51, 0xFE52, 0xFE53, 0xFE54, 0xFE55, 0xFE56, 0xFE57,
1855 0xFE58, 0xFE59, 0xFE5A, 0xFE5B, 0xFE5C, 0xFE5D, 0xFE5E, 0xFE5F,
1856 0xFE60, 0xFE61, 0xFE62, 0xFE63, 0xFE64, 0xFE65, 0xFE66, 0xFE67,
1857 0xFE68, 0xFE69, 0xFE6A, 0xFE6B, 0xFE6C, 0xFE6D, 0xFE6E, 0xFE6F,
1858 0xFE70, 0xFE71, 0xFE72, 0xFE73, 0xFE74, 0xFE75, 0xFE76, 0xFE77,
1859 0xFE78, 0xFE79, 0xFE7A, 0xFE7B, 0xFE7C, 0xFE7D, 0xFE7E, 0xFE7F,
1860 0xFE80, 0xFE81, 0xFE82, 0xFE83, 0xFE84, 0xFE85, 0xFE86, 0xFE87,
1861 0xFE88, 0xFE89, 0xFE8A, 0xFE8B, 0xFE8C, 0xFE8D, 0xFE8E, 0xFE8F,
1862 0xFE90, 0xFE91, 0xFE92, 0xFE93, 0xFE94, 0xFE95, 0xFE96, 0xFE97,
1863 0xFE98, 0xFE99, 0xFE9A, 0xFE9B, 0xFE9C, 0xFE9D, 0xFE9E, 0xFE9F,
1864 0xFEA0, 0xFEA1, 0xFEA2, 0xFEA3, 0xFEA4, 0xFEA5, 0xFEA6, 0xFEA7,
1865 0xFEA8, 0xFEA9, 0xFEAA, 0xFEAB, 0xFEAC, 0xFEAD, 0xFEAE, 0xFEAF,
1866 0xFEB0, 0xFEB1, 0xFEB2, 0xFEB3, 0xFEB4, 0xFEB5, 0xFEB6, 0xFEB7,
1867 0xFEB8, 0xFEB9, 0xFEBA, 0xFEBB, 0xFEBC, 0xFEBD, 0xFEBE, 0xFEBF,
1868 0xFEC0, 0xFEC1, 0xFEC2, 0xFEC3, 0xFEC4, 0xFEC5, 0xFEC6, 0xFEC7,
1869 0xFEC8, 0xFEC9, 0xFECA, 0xFECB, 0xFECC, 0xFECD, 0xFECE, 0xFECF,
1870 0xFED0, 0xFED1, 0xFED2, 0xFED3, 0xFED4, 0xFED5, 0xFED6, 0xFED7,
1871 0xFED8, 0xFED9, 0xFEDA, 0xFEDB, 0xFEDC, 0xFEDD, 0xFEDE, 0xFEDF,
1872 0xFEE0, 0xFEE1, 0xFEE2, 0xFEE3, 0xFEE4, 0xFEE5, 0xFEE6, 0xFEE7,
1873 0xFEE8, 0xFEE9, 0xFEEA, 0xFEEB, 0xFEEC, 0xFEED, 0xFEEE, 0xFEEF,
1874 0xFEF0, 0xFEF1, 0xFEF2, 0xFEF3, 0xFEF4, 0xFEF5, 0xFEF6, 0xFEF7,
1875 0xFEF8, 0xFEF9, 0xFEFA, 0xFEFB, 0xFEFC, 0xFEFD, 0xFEFE, 0x0000,
1876
1877 /* Table 10 (for high byte 0xFF) */
1878
1879 0xFF00, 0xFF01, 0xFF02, 0xFF03, 0xFF04, 0xFF05, 0xFF06, 0xFF07,
1880 0xFF08, 0xFF09, 0xFF0A, 0xFF0B, 0xFF0C, 0xFF0D, 0xFF0E, 0xFF0F,
1881 0xFF10, 0xFF11, 0xFF12, 0xFF13, 0xFF14, 0xFF15, 0xFF16, 0xFF17,
1882 0xFF18, 0xFF19, 0xFF1A, 0xFF1B, 0xFF1C, 0xFF1D, 0xFF1E, 0xFF1F,
1883 0xFF20, 0xFF41, 0xFF42, 0xFF43, 0xFF44, 0xFF45, 0xFF46, 0xFF47,
1884 0xFF48, 0xFF49, 0xFF4A, 0xFF4B, 0xFF4C, 0xFF4D, 0xFF4E, 0xFF4F,
1885 0xFF50, 0xFF51, 0xFF52, 0xFF53, 0xFF54, 0xFF55, 0xFF56, 0xFF57,
1886 0xFF58, 0xFF59, 0xFF5A, 0xFF3B, 0xFF3C, 0xFF3D, 0xFF3E, 0xFF3F,
1887 0xFF40, 0xFF41, 0xFF42, 0xFF43, 0xFF44, 0xFF45, 0xFF46, 0xFF47,
1888 0xFF48, 0xFF49, 0xFF4A, 0xFF4B, 0xFF4C, 0xFF4D, 0xFF4E, 0xFF4F,
1889 0xFF50, 0xFF51, 0xFF52, 0xFF53, 0xFF54, 0xFF55, 0xFF56, 0xFF57,
1890 0xFF58, 0xFF59, 0xFF5A, 0xFF5B, 0xFF5C, 0xFF5D, 0xFF5E, 0xFF5F,
1891 0xFF60, 0xFF61, 0xFF62, 0xFF63, 0xFF64, 0xFF65, 0xFF66, 0xFF67,
1892 0xFF68, 0xFF69, 0xFF6A, 0xFF6B, 0xFF6C, 0xFF6D, 0xFF6E, 0xFF6F,
1893 0xFF70, 0xFF71, 0xFF72, 0xFF73, 0xFF74, 0xFF75, 0xFF76, 0xFF77,
1894 0xFF78, 0xFF79, 0xFF7A, 0xFF7B, 0xFF7C, 0xFF7D, 0xFF7E, 0xFF7F,
1895 0xFF80, 0xFF81, 0xFF82, 0xFF83, 0xFF84, 0xFF85, 0xFF86, 0xFF87,
1896 0xFF88, 0xFF89, 0xFF8A, 0xFF8B, 0xFF8C, 0xFF8D, 0xFF8E, 0xFF8F,
1897 0xFF90, 0xFF91, 0xFF92, 0xFF93, 0xFF94, 0xFF95, 0xFF96, 0xFF97,
1898 0xFF98, 0xFF99, 0xFF9A, 0xFF9B, 0xFF9C, 0xFF9D, 0xFF9E, 0xFF9F,
1899 0xFFA0, 0xFFA1, 0xFFA2, 0xFFA3, 0xFFA4, 0xFFA5, 0xFFA6, 0xFFA7,
1900 0xFFA8, 0xFFA9, 0xFFAA, 0xFFAB, 0xFFAC, 0xFFAD, 0xFFAE, 0xFFAF,
1901 0xFFB0, 0xFFB1, 0xFFB2, 0xFFB3, 0xFFB4, 0xFFB5, 0xFFB6, 0xFFB7,
1902 0xFFB8, 0xFFB9, 0xFFBA, 0xFFBB, 0xFFBC, 0xFFBD, 0xFFBE, 0xFFBF,
1903 0xFFC0, 0xFFC1, 0xFFC2, 0xFFC3, 0xFFC4, 0xFFC5, 0xFFC6, 0xFFC7,
1904 0xFFC8, 0xFFC9, 0xFFCA, 0xFFCB, 0xFFCC, 0xFFCD, 0xFFCE, 0xFFCF,
1905 0xFFD0, 0xFFD1, 0xFFD2, 0xFFD3, 0xFFD4, 0xFFD5, 0xFFD6, 0xFFD7,
1906 0xFFD8, 0xFFD9, 0xFFDA, 0xFFDB, 0xFFDC, 0xFFDD, 0xFFDE, 0xFFDF,
1907 0xFFE0, 0xFFE1, 0xFFE2, 0xFFE3, 0xFFE4, 0xFFE5, 0xFFE6, 0xFFE7,
1908 0xFFE8, 0xFFE9, 0xFFEA, 0xFFEB, 0xFFEC, 0xFFED, 0xFFEE, 0xFFEF,
1909 0xFFF0, 0xFFF1, 0xFFF2, 0xFFF3, 0xFFF4, 0xFFF5, 0xFFF6, 0xFFF7,
1910 0xFFF8, 0xFFF9, 0xFFFA, 0xFFFB, 0xFFFC, 0xFFFD, 0xFFFE, 0xFFFF,
1911 };
1912
1913 static int
1914 hfsfold(int c)
1915 {
1916 int i;
1917
1918 i = hfslcase[(c>>8)&255];
1919 if(i == 0)
1920 return c;
1921 return hfslcase[i+(c&255)];
1922 }
1923
1924 static int
1925 hfsinamecmp(Name *a, Name *b)
1926 {
1927 int an, bn, ac, bc, diff;
1928 Rune *ap, *bp;
1929
1930 an = a->len;
1931 ap = a->name;
1932 bn = b->len;
1933 bp = b->name;
1934 for(;;){
1935 ac = 0;
1936 while(an && !ac){
1937 ac = hfsfold(*ap);
1938 ap++;
1939 an--;
1940 }
1941 bc = 0;
1942 while(bn && !bc){
1943 bc = hfsfold(*bp);
1944 bp++;
1945 bn--;
1946 }
1947 diff = ac - bc;
1948 if(diff)
1949 return diff;
1950 if(ac == 0)
1951 return 0;
1952 }
1953 }
1954
1955 static int
1956 hfsnamecmp(Name *a, Name *b)
1957 {
1958 int n, diff;
1959 Rune *ap, *bp;
1960
1961 n = a->len;
1962 if(n > b->len)
1963 n = b->len;
1964 ap = a->name;
1965 bp = b->name;
1966 diff = 0;
1967 for(; n>0; n--, ap++, bp++){
1968 diff = *ap - *bp;
1969 if(diff)
1970 break;
1971 }
1972 if(diff == 0)
1973 diff = a->len - b->len;
1974 return diff;
1975 }