1 /* $OpenBSD: parse.y,v 1.9 2024/06/06 06:26:14 florian Exp $ */
2
3 /*
4 * Copyright (c) 2018, 2024 Florian Obser <florian@openbsd.org>
5 * Copyright (c) 2004, 2005 Esben Norby <norby@openbsd.org>
6 * Copyright (c) 2004 Ryan McBride <mcbride@openbsd.org>
7 * Copyright (c) 2002, 2003, 2004 Henning Brauer <henning@openbsd.org>
8 * Copyright (c) 2001 Markus Friedl. All rights reserved.
9 * Copyright (c) 2001 Daniel Hartmeier. All rights reserved.
10 * Copyright (c) 2001 Theo de Raadt. All rights reserved.
11 *
12 * Permission to use, copy, modify, and distribute this software for any
13 * purpose with or without fee is hereby granted, provided that the above
14 * copyright notice and this permission notice appear in all copies.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
17 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
18 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
19 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
20 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
21 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
22 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
23 */
24
25 %{
26 #include <sys/types.h>
27 #include <sys/queue.h>
28 #include <sys/socket.h>
29 #include <sys/stat.h>
30
31 #include <net/if.h>
32
33 #include <netinet/in.h>
34
35 #include <arpa/inet.h>
36
37 #include <ctype.h>
38 #include <err.h>
39 #include <errno.h>
40 #include <event.h>
41 #include <imsg.h>
42 #include <limits.h>
43 #include <stdarg.h>
44 #include <stdio.h>
45 #include <string.h>
46 #include <syslog.h>
47 #include <unistd.h>
48 #include <vis.h>
49
50 #include "log.h"
51 #include "dhcp6leased.h"
52 #include "frontend.h"
53
54 TAILQ_HEAD(files, file) files = TAILQ_HEAD_INITIALIZER(files);
55 struct file *file, *topfile;
56 int check_file_secrecy(int, const char *);
57 int yyparse(void);
58 int yylex(void);
59 int yyerror(const char *, ...)
60 __attribute__((__format__ (printf, 1, 2)))
61 __attribute__((__nonnull__ (1)));
62 int lookup(char *);
63 int igetc(void);
64
65 TAILQ_HEAD(symhead, sym) symhead = TAILQ_HEAD_INITIALIZER(symhead);
66 struct sym {
67 TAILQ_ENTRY(sym) entry;
68 int used;
69 int persist;
70 char *nam;
71 char *val;
72 };
73
74 int symset(const char *, const char *, int);
75 char *symget(const char *);
76
77 static struct dhcp6leased_conf *conf;
78 static int errors;
79
80 static struct iface_conf *iface_conf;
81 static struct iface_ia_conf *iface_ia_conf;
82
83 struct iface_conf *conf_get_iface(char *);
84 struct iface_pd_conf *conf_get_pd_iface(char *, int);
85 void addressing_plan(struct iface_ia_conf *);
86 int fls64(uint64_t);
87
88 typedef struct {
89 union {
90 int64_t number;
91 char *string;
92 } v;
93 int lineno;
94 } YYSTYPE;
95
96 %}
97
98 %token ERROR DELEGATION FOR ON PREFIX REQUEST RAPID COMMIT
99
100 %token <v.string> STRING
101 %token <v.number> NUMBER
102 %type <v.string> string
103
104 %%
105
106 grammar : /* empty */
107 | grammar '\n'
108 | grammar varset '\n'
109 | grammar conf_main '\n'
110 | grammar ia_pd '\n'
111 | grammar error '\n' { file->errors++; }
112 ;
113
114 string : string STRING {
115 if (asprintf(&$$, "%s %s", $1, $2) == -1) {
116 free($1);
117 free($2);
118 yyerror("string: asprintf");
119 YYERROR;
120 }
121 free($1);
122 free($2);
123 }
124 | STRING
125 ;
126
127 varset : STRING '=' string {
128 char *s = $1;
129 if (log_getverbose() == 1)
130 printf("%s = \"%s\"\n", $1, $3);
131 while (*s++) {
132 if (isspace((unsigned char)*s)) {
133 yyerror("macro name cannot contain "
134 "whitespace");
135 free($1);
136 free($3);
137 YYERROR;
138 }
139 }
140 if (symset($1, $3, 0) == -1)
141 fatal("cannot store variable");
142 free($1);
143 free($3);
144 }
145 ;
146
147 optnl : '\n' optnl /* zero or more newlines */
148 | /*empty*/
149 ;
150
151 nl : '\n' optnl /* one or more newlines */
152 ;
153 conf_main : REQUEST RAPID COMMIT {
154 conf->rapid_commit = 1;
155 }
156 ;
157
158 ia_pd : REQUEST PREFIX DELEGATION ON STRING FOR {
159 iface_conf = conf_get_iface($5);
160 iface_ia_conf = calloc(1, sizeof(*iface_ia_conf));
161 if (iface_ia_conf == NULL)
162 err(1, "%s: calloc", __func__);
163 iface_ia_conf->id = iface_conf->ia_count++;
164 if (iface_conf->ia_count > MAX_IA) {
165 yyerror("Too many prefix delegation requests");
166 YYERROR;
167 }
168 SIMPLEQ_INIT(&iface_ia_conf->iface_pd_list);
169 SIMPLEQ_INSERT_TAIL(&iface_conf->iface_ia_list,
170 iface_ia_conf, entry);
171 } iface_block {
172 iface_conf = NULL;
173 iface_ia_conf = NULL;
174 }
175 ;
176
177 iface_block : '{' optnl ifaceopts_l '}'
178 | ifaceoptsl
179 ;
180
181 ifaceopts_l : ifaceopts_l ifaceoptsl optnl
182 | ifaceoptsl optnl
183 ;
184
185 ifaceoptsl : STRING {
186 struct iface_pd_conf *iface_pd_conf;
187 int prefixlen;
188 char *p;
189 const char *errstr;
190
191 p = strchr($1, '/');
192 if (p != NULL) {
193 *p++ = '\0';
194 prefixlen = strtonum(p, 0, 128, &errstr);
195 if (errstr != NULL) {
196 yyerror("error parsing interface "
197 "\"%s/%s\"", $1, p);
198 free($1);
199 YYERROR;
200 }
201 } else
202 prefixlen = 64;
203 if ((iface_pd_conf = conf_get_pd_iface($1, prefixlen))
204 == NULL) {
205 yyerror("duplicate interface %s", $1);
206 free($1);
207 YYERROR;
208 }
209 }
210 ;
211 %%
212
213 struct keywords {
214 const char *k_name;
215 int k_val;
216 };
217
218 int
yyerror(const char * fmt,...)219 yyerror(const char *fmt, ...)
220 {
221 va_list ap;
222 char *msg;
223
224 file->errors++;
225 va_start(ap, fmt);
226 if (vasprintf(&msg, fmt, ap) == -1)
227 fatalx("yyerror vasprintf");
228 va_end(ap);
229 logit(LOG_CRIT, "%s:%d: %s", file->name, yylval.lineno, msg);
230 free(msg);
231 return (0);
232 }
233
234 int
kw_cmp(const void * k,const void * e)235 kw_cmp(const void *k, const void *e)
236 {
237 return (strcmp(k, ((const struct keywords *)e)->k_name));
238 }
239
240 int
lookup(char * s)241 lookup(char *s)
242 {
243 /* This has to be sorted always. */
244 static const struct keywords keywords[] = {
245 {"commit", COMMIT},
246 {"delegation", DELEGATION},
247 {"for", FOR},
248 {"on", ON},
249 {"prefix", PREFIX},
250 {"rapid", RAPID},
251 {"request", REQUEST},
252 };
253 const struct keywords *p;
254
255 p = bsearch(s, keywords, sizeof(keywords)/sizeof(keywords[0]),
256 sizeof(keywords[0]), kw_cmp);
257
258 if (p)
259 return (p->k_val);
260 else
261 return (STRING);
262 }
263
264 #define START_EXPAND 1
265 #define DONE_EXPAND 2
266
267 static int expanding;
268
269 int
igetc(void)270 igetc(void)
271 {
272 int c;
273
274 while (1) {
275 if (file->ungetpos > 0)
276 c = file->ungetbuf[--file->ungetpos];
277 else
278 c = getc(file->stream);
279
280 if (c == START_EXPAND)
281 expanding = 1;
282 else if (c == DONE_EXPAND)
283 expanding = 0;
284 else
285 break;
286 }
287 return (c);
288 }
289
290 int
lgetc(int quotec)291 lgetc(int quotec)
292 {
293 int c, next;
294
295 if (quotec) {
296 if ((c = igetc()) == EOF) {
297 yyerror("reached end of file while parsing "
298 "quoted string");
299 if (file == topfile || popfile() == EOF)
300 return (EOF);
301 return (quotec);
302 }
303 return (c);
304 }
305
306 while ((c = igetc()) == '\\') {
307 next = igetc();
308 if (next != '\n') {
309 c = next;
310 break;
311 }
312 yylval.lineno = file->lineno;
313 file->lineno++;
314 }
315
316 if (c == EOF) {
317 /*
318 * Fake EOL when hit EOF for the first time. This gets line
319 * count right if last line in included file is syntactically
320 * invalid and has no newline.
321 */
322 if (file->eof_reached == 0) {
323 file->eof_reached = 1;
324 return ('\n');
325 }
326 while (c == EOF) {
327 if (file == topfile || popfile() == EOF)
328 return (EOF);
329 c = igetc();
330 }
331 }
332 return (c);
333 }
334
335 void
lungetc(int c)336 lungetc(int c)
337 {
338 if (c == EOF)
339 return;
340
341 if (file->ungetpos >= file->ungetsize) {
342 void *p = reallocarray(file->ungetbuf, file->ungetsize, 2);
343 if (p == NULL)
344 err(1, "lungetc");
345 file->ungetbuf = p;
346 file->ungetsize *= 2;
347 }
348 file->ungetbuf[file->ungetpos++] = c;
349 }
350
351 int
findeol(void)352 findeol(void)
353 {
354 int c;
355
356 /* Skip to either EOF or the first real EOL. */
357 while (1) {
358 c = lgetc(0);
359 if (c == '\n') {
360 file->lineno++;
361 break;
362 }
363 if (c == EOF)
364 break;
365 }
366 return (ERROR);
367 }
368
369 int
yylex(void)370 yylex(void)
371 {
372 char buf[8096];
373 char *p, *val;
374 int quotec, next, c;
375 int token;
376
377 top:
378 p = buf;
379 while ((c = lgetc(0)) == ' ' || c == '\t')
380 ; /* nothing */
381
382 yylval.lineno = file->lineno;
383 if (c == '#')
384 while ((c = lgetc(0)) != '\n' && c != EOF)
385 ; /* nothing */
386 if (c == '$' && !expanding) {
387 while (1) {
388 if ((c = lgetc(0)) == EOF)
389 return (0);
390
391 if (p + 1 >= buf + sizeof(buf) - 1) {
392 yyerror("string too long");
393 return (findeol());
394 }
395 if (isalnum(c) || c == '_') {
396 *p++ = c;
397 continue;
398 }
399 *p = '\0';
400 lungetc(c);
401 break;
402 }
403 val = symget(buf);
404 if (val == NULL) {
405 yyerror("macro '%s' not defined", buf);
406 return (findeol());
407 }
408 p = val + strlen(val) - 1;
409 lungetc(DONE_EXPAND);
410 while (p >= val) {
411 lungetc((unsigned char)*p);
412 p--;
413 }
414 lungetc(START_EXPAND);
415 goto top;
416 }
417
418 switch (c) {
419 case '\'':
420 case '"':
421 quotec = c;
422 while (1) {
423 if ((c = lgetc(quotec)) == EOF)
424 return (0);
425 if (c == '\n') {
426 file->lineno++;
427 continue;
428 } else if (c == '\\') {
429 if ((next = lgetc(quotec)) == EOF)
430 return (0);
431 if (next == quotec || next == ' ' ||
432 next == '\t')
433 c = next;
434 else if (next == '\n') {
435 file->lineno++;
436 continue;
437 } else
438 lungetc(next);
439 } else if (c == quotec) {
440 *p = '\0';
441 break;
442 } else if (c == '\0') {
443 yyerror("syntax error");
444 return (findeol());
445 }
446 if (p + 1 >= buf + sizeof(buf) - 1) {
447 yyerror("string too long");
448 return (findeol());
449 }
450 *p++ = c;
451 }
452 yylval.v.string = strdup(buf);
453 if (yylval.v.string == NULL)
454 err(1, "yylex: strdup");
455 return (STRING);
456 }
457
458 #define allowed_to_end_number(x) \
459 (isspace(x) || x == ')' || x ==',' || x == '/' || x == '}' || x == '=')
460
461 if (c == '-' || isdigit(c)) {
462 do {
463 *p++ = c;
464 if ((size_t)(p-buf) >= sizeof(buf)) {
465 yyerror("string too long");
466 return (findeol());
467 }
468 } while ((c = lgetc(0)) != EOF && isdigit(c));
469 lungetc(c);
470 if (p == buf + 1 && buf[0] == '-')
471 goto nodigits;
472 if (c == EOF || allowed_to_end_number(c)) {
473 const char *errstr = NULL;
474
475 *p = '\0';
476 yylval.v.number = strtonum(buf, LLONG_MIN,
477 LLONG_MAX, &errstr);
478 if (errstr) {
479 yyerror("\"%s\" invalid number: %s",
480 buf, errstr);
481 return (findeol());
482 }
483 return (NUMBER);
484 } else {
485 nodigits:
486 while (p > buf + 1)
487 lungetc((unsigned char)*--p);
488 c = (unsigned char)*--p;
489 if (c == '-')
490 return (c);
491 }
492 }
493
494 #define allowed_in_string(x) \
495 (isalnum(x) || (ispunct(x) && x != '(' && x != ')' && \
496 x != '{' && x != '}' && \
497 x != '!' && x != '=' && x != '#' && \
498 x != ','))
499
500 if (isalnum(c) || c == ':' || c == '_') {
501 do {
502 *p++ = c;
503 if ((size_t)(p-buf) >= sizeof(buf)) {
504 yyerror("string too long");
505 return (findeol());
506 }
507 } while ((c = lgetc(0)) != EOF && (allowed_in_string(c)));
508 lungetc(c);
509 *p = '\0';
510 if ((token = lookup(buf)) == STRING)
511 if ((yylval.v.string = strdup(buf)) == NULL)
512 err(1, "yylex: strdup");
513 return (token);
514 }
515 if (c == '\n') {
516 yylval.lineno = file->lineno;
517 file->lineno++;
518 }
519 if (c == EOF)
520 return (0);
521 return (c);
522 }
523
524 int
check_file_secrecy(int fd,const char * fname)525 check_file_secrecy(int fd, const char *fname)
526 {
527 struct stat st;
528
529 if (fstat(fd, &st)) {
530 log_warn("cannot stat %s", fname);
531 return (-1);
532 }
533 if (st.st_uid != 0 && st.st_uid != getuid()) {
534 log_warnx("%s: owner not root or current user", fname);
535 return (-1);
536 }
537 if (st.st_mode & (S_IWGRP | S_IXGRP | S_IRWXO)) {
538 log_warnx("%s: group writable or world read/writable", fname);
539 return (-1);
540 }
541 return (0);
542 }
543
544 struct file *
pushfile(const char * name,int secret)545 pushfile(const char *name, int secret)
546 {
547 struct file *nfile;
548
549 if ((nfile = calloc(1, sizeof(struct file))) == NULL) {
550 log_warn("calloc");
551 return (NULL);
552 }
553 if ((nfile->name = strdup(name)) == NULL) {
554 log_warn("strdup");
555 free(nfile);
556 return (NULL);
557 }
558 if ((nfile->stream = fopen(nfile->name, "r")) == NULL) {
559 free(nfile->name);
560 free(nfile);
561 return (NULL);
562 } else if (secret &&
563 check_file_secrecy(fileno(nfile->stream), nfile->name)) {
564 fclose(nfile->stream);
565 free(nfile->name);
566 free(nfile);
567 return (NULL);
568 }
569 nfile->lineno = TAILQ_EMPTY(&files) ? 1 : 0;
570 nfile->ungetsize = 16;
571 nfile->ungetbuf = malloc(nfile->ungetsize);
572 if (nfile->ungetbuf == NULL) {
573 log_warn("malloc");
574 fclose(nfile->stream);
575 free(nfile->name);
576 free(nfile);
577 return (NULL);
578 }
579 TAILQ_INSERT_TAIL(&files, nfile, entry);
580 return (nfile);
581 }
582
583 int
popfile(void)584 popfile(void)
585 {
586 struct file *prev;
587
588 if ((prev = TAILQ_PREV(file, files, entry)) != NULL)
589 prev->errors += file->errors;
590
591 TAILQ_REMOVE(&files, file, entry);
592 fclose(file->stream);
593 free(file->name);
594 free(file->ungetbuf);
595 free(file);
596 file = prev;
597 return (file ? 0 : EOF);
598 }
599
600 struct dhcp6leased_conf *
parse_config(const char * filename)601 parse_config(const char *filename)
602 {
603 struct sym *sym, *next;
604 struct iface_conf *iface;
605 struct iface_ia_conf *ia_conf;
606
607 conf = config_new_empty();
608
609 file = pushfile(filename, 0);
610 if (file == NULL) {
611 free(conf);
612 return (NULL);
613 }
614 topfile = file;
615
616 yyparse();
617 errors = file->errors;
618 popfile();
619
620 /* Free macros and check which have not been used. */
621 TAILQ_FOREACH_SAFE(sym, &symhead, entry, next) {
622 if ((log_getverbose() == 2) && !sym->used)
623 fprintf(stderr, "warning: macro '%s' not used\n",
624 sym->nam);
625 if (!sym->persist) {
626 free(sym->nam);
627 free(sym->val);
628 TAILQ_REMOVE(&symhead, sym, entry);
629 free(sym);
630 }
631 }
632
633 if (errors) {
634 config_clear(conf);
635 return (NULL);
636 }
637
638 SIMPLEQ_FOREACH(iface, &conf->iface_list, entry) {
639 SIMPLEQ_FOREACH(ia_conf, &iface->iface_ia_list, entry) {
640 addressing_plan(ia_conf);
641 }
642 }
643 return (conf);
644 }
645
646 int
symset(const char * nam,const char * val,int persist)647 symset(const char *nam, const char *val, int persist)
648 {
649 struct sym *sym;
650
651 TAILQ_FOREACH(sym, &symhead, entry) {
652 if (strcmp(nam, sym->nam) == 0)
653 break;
654 }
655
656 if (sym != NULL) {
657 if (sym->persist == 1)
658 return (0);
659 else {
660 free(sym->nam);
661 free(sym->val);
662 TAILQ_REMOVE(&symhead, sym, entry);
663 free(sym);
664 }
665 }
666 if ((sym = calloc(1, sizeof(*sym))) == NULL)
667 return (-1);
668
669 sym->nam = strdup(nam);
670 if (sym->nam == NULL) {
671 free(sym);
672 return (-1);
673 }
674 sym->val = strdup(val);
675 if (sym->val == NULL) {
676 free(sym->nam);
677 free(sym);
678 return (-1);
679 }
680 sym->used = 0;
681 sym->persist = persist;
682 TAILQ_INSERT_TAIL(&symhead, sym, entry);
683 return (0);
684 }
685
686 char *
symget(const char * nam)687 symget(const char *nam)
688 {
689 struct sym *sym;
690
691 TAILQ_FOREACH(sym, &symhead, entry) {
692 if (strcmp(nam, sym->nam) == 0) {
693 sym->used = 1;
694 return (sym->val);
695 }
696 }
697 return (NULL);
698 }
699
700 struct iface_conf *
conf_get_iface(char * name)701 conf_get_iface(char *name)
702 {
703 struct iface_conf *iface;
704 size_t n;
705
706 SIMPLEQ_FOREACH(iface, &conf->iface_list, entry) {
707 if (strcmp(name, iface->name) == 0)
708 return (iface);
709 }
710
711 iface = calloc(1, sizeof(*iface));
712 if (iface == NULL)
713 errx(1, "%s: calloc", __func__);
714 n = strlcpy(iface->name, name, sizeof(iface->name));
715 if (n >= sizeof(iface->name))
716 errx(1, "%s: name too long", __func__);
717 SIMPLEQ_INIT(&iface->iface_ia_list);
718
719 SIMPLEQ_INSERT_TAIL(&conf->iface_list, iface, entry);
720
721 return (iface);
722 }
723
724 struct iface_pd_conf *
conf_get_pd_iface(char * name,int prefixlen)725 conf_get_pd_iface(char *name, int prefixlen)
726 {
727 struct iface_ia_conf *iface_ia;
728 struct iface_pd_conf *iface_pd;
729 size_t n;
730
731 if (strcmp(name, "reserve") != 0) {
732 SIMPLEQ_FOREACH(iface_ia, &iface_conf->iface_ia_list,
733 entry) {
734 SIMPLEQ_FOREACH(iface_pd, &iface_ia->iface_pd_list,
735 entry) {
736 if (strcmp(name, iface_pd->name) == 0)
737 return NULL;
738 }
739 }
740 }
741
742 iface_pd = calloc(1, sizeof(*iface_pd));
743 if (iface_pd == NULL)
744 err(1, "%s: calloc", __func__);
745 n = strlcpy(iface_pd->name, name, sizeof(iface_pd->name));
746 if (n >= sizeof(iface_pd->name))
747 errx(1, "%s: name too long", __func__);
748 iface_pd->prefix_len = prefixlen;
749
750 SIMPLEQ_INSERT_TAIL(&iface_ia_conf->iface_pd_list, iface_pd, entry);
751
752 return (iface_pd);
753 }
754
755 static inline uint64_t
get_shift(int plen)756 get_shift(int plen)
757 {
758 if (plen > 64)
759 plen -= 64;
760
761 return 1ULL << (64 - plen);
762 }
763
764 void
addressing_plan(struct iface_ia_conf * ia_conf)765 addressing_plan(struct iface_ia_conf *ia_conf)
766 {
767 struct iface_pd_conf *pd_conf;
768 uint64_t *p, lo_counter, hi_counter, lo_shift, hi_shift;
769 int prev_plen = -1;
770
771 lo_counter = hi_counter = 0;
772
773 SIMPLEQ_FOREACH(pd_conf, &ia_conf->iface_pd_list, entry) {
774 /* not the first prefix */
775 if (ia_conf->prefix_len != 0) {
776 lo_shift = hi_shift = 0;
777 if (prev_plen > pd_conf->prefix_len) {
778 if (pd_conf->prefix_len > 64)
779 lo_shift =
780 get_shift(pd_conf->prefix_len);
781 else
782 hi_shift =
783 get_shift(pd_conf->prefix_len);
784 } else {
785 if (prev_plen > 64)
786 lo_shift = get_shift(prev_plen);
787 else
788 hi_shift = get_shift(prev_plen);
789 }
790
791 if (lo_shift != 0) {
792 if (lo_counter > UINT64_MAX - lo_shift) {
793 /* overflow */
794 hi_counter++;
795 lo_counter = 0;
796 } else {
797 lo_counter += lo_shift;
798 /* remove all lower bits */
799 lo_counter &= ~(lo_shift - 1);
800 }
801 } else {
802 hi_counter += hi_shift;
803 /* remove all lower bits */
804 hi_counter &= ~(hi_shift - 1);
805 lo_counter = 0;
806 }
807
808 } else
809 ia_conf->prefix_len = pd_conf->prefix_len;
810
811 p = (uint64_t *)&pd_conf->prefix_mask.s6_addr;
812 *p |= htobe64(hi_counter);
813
814 p = (uint64_t *)&pd_conf->prefix_mask.s6_addr[8];
815 *p |= htobe64(lo_counter);
816
817 prev_plen = pd_conf->prefix_len;
818 }
819
820 if (hi_counter != 0)
821 ia_conf->prefix_len = 64 - fls64(hi_counter);
822 else if (lo_counter != 0)
823 ia_conf->prefix_len = 128 - fls64(lo_counter);
824 }
825
826 /* from NetBSD's sys/sys/bitops.h */
827 /*-
828 * Copyright (c) 2007, 2010 The NetBSD Foundation, Inc.
829 * All rights reserved.
830 *
831 * This code is derived from software contributed to The NetBSD Foundation
832 * by Christos Zoulas and Joerg Sonnenberger.
833 *
834 * Redistribution and use in source and binary forms, with or without
835 * modification, are permitted provided that the following conditions
836 * are met:
837 * 1. Redistributions of source code must retain the above copyright
838 * notice, this list of conditions and the following disclaimer.
839 * 2. Redistributions in binary form must reproduce the above copyright
840 * notice, this list of conditions and the following disclaimer in the
841 * documentation and/or other materials provided with the distribution.
842 *
843 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
844 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
845 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
846 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
847 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
848 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
849 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
850 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
851 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
852 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
853 * POSSIBILITY OF SUCH DAMAGE.
854 */
855 int
fls64(uint64_t _n)856 fls64(uint64_t _n)
857 {
858 int _v;
859
860 if (!_n)
861 return 0;
862
863 _v = 64;
864 if ((_n & 0xFFFFFFFF00000000ULL) == 0) {
865 _n <<= 32;
866 _v -= 32;
867 }
868 if ((_n & 0xFFFF000000000000ULL) == 0) {
869 _n <<= 16;
870 _v -= 16;
871 }
872 if ((_n & 0xFF00000000000000ULL) == 0) {
873 _n <<= 8;
874 _v -= 8;
875 }
876 if ((_n & 0xF000000000000000ULL) == 0) {
877 _n <<= 4;
878 _v -= 4;
879 }
880 if ((_n & 0xC000000000000000ULL) == 0) {
881 _n <<= 2;
882 _v -= 2;
883 }
884 if ((_n & 0x8000000000000000ULL) == 0) {
885 //_n <<= 1;
886 _v -= 1;
887 }
888 return _v;
889 }
890