summaryrefslogtreecommitdiffstats
path: root/qemu/roms/ipxe/src/crypto/deflate.c
blob: 91a4899610c60bb9d4635dfb28d7a7a0d65c4f9e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

@media only all and (prefers-color-scheme: dark) {
.highlight .hll { background-color: #49483e }
.highlight .c { color: #75715e } /* Comment */
.highlight .err { color: #960050; background-color: #1e0010 } /* Error */
.highlight .k { color: #66d9ef } /* Keyword */
.highlight .l { color: #ae81ff } /* Literal */
.highlight .n { color: #f8f8f2 } /* Name */
.highlight .o { color: #f92672 } /* Operator */
.highlight .p { color: #f8f8f2 } /* Punctuation */
.highlight .ch { color: #75715e } /* Comment.Hashbang */
.highlight .cm { color: #75715e } /* Comment.Multiline */
.highlight .cp { color: #75715e } /* Comment.Preproc */
.highlight .cpf { color: #75715e } /* Comment.PreprocFile */
.highlight .c1 { color: #75715e } /* Comment.Single */
.highlight .cs { color: #75715e } /* Comment.Special */
.highlight .gd { color: #f92672 } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .gi { color: #a6e22e } /* Generic.Inserted */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #75715e } /* Generic.Subheading */
.highlight .kc { color: #66d9ef } /* Keyword.Constant */
.highlight .kd { color: #66d9ef } /* Keyword.Declaration */
.highlight .kn { color: #f92672 } /* Keyword.Namespace */
.highlight .kp { color: #66d9ef } /* Keyword.Pseudo */
.highlight .kr { color: #66d9ef } /* Keyword.Reserved */
.highlight .kt { color: #66d9ef } /* Keyword.Type */
.highlight .ld { color: #e6db74 } /* Literal.Date */
.highlight .m { color: #ae81ff } /* Literal.Number */
.highlight .s { color: #e6db74 } /* Literal.String */
.highlight .na { color: #a6e22e } /* Name.Attribute */
.highlight .nb { color: #f8f8f2 } /* Name.Builtin */
.highlight .nc { color: #a6e22e } /* Name.Class */
.highlight .no { color: #66d9ef } /* Name.Constant */
.highlight .nd { color: #a6e22e } /* Name.Decorator */
.highlight .ni { color: #f8f8f2 } /* Name.Entity */
.highlight .ne { color: #a6e22e } /* Name.Exception */
.highlight .nf { color: #a6e22e } /* Name.Function */
.highlight .nl { color: #f8f8f2 } /* Name.Label */
.highlight .nn { color: #f8f8f2 } /* Name.Namespace */
.highlight .nx { color: #a6e22e } /* Name.Other */
.highlight .py { color: #f8f8f2 } /* Name.Property */
.highlight .nt { color: #f92672 } /* Name.Tag */
.highlight .nv { color: #f8f8f2 } /* Name.Variable */
.highlight .ow { color: #f92672 } /* Operator.Word */
.highlight .w { color: #f8f8f2 } /* Text.Whitespace */
.highlight .mb { color: #ae81ff } /* Literal.Number.Bin */
.highlight .mf { color: #ae81ff } /* Literal.Number.Float */
.highlight .mh { color: #ae81ff } /* Literal.Number.Hex */
.highlight .mi { color: #ae81ff } /* Literal.Number.Integer */
.highlight .mo { color: #ae81ff } /* Literal.Number.Oct */
.highlight .sa { color: #e6db74 } /* Literal.String.Affix */
.highlight .sb { color: #e6db74 } /* Literal.String.Backtick */
.highlight .sc { color: #e6db74 } /* Literal.String.Char */
.highlight .dl { color: #e6db74 } /* Literal.String.Delimiter */
.highlight .sd { color: #e6db74 } /* Literal.String.Doc */
.highlight .s2 { color: #e6db74 } /* Literal.String.Double */
.highlight .se { color: #ae81ff } /* Literal.String.Escape */
.highlight .sh { color: #e6db74 } /* Literal.String.Heredoc */
.highlight .si { color: #e6db74 } /* Literal.String.Interpol */
.highlight .sx { color: #e6db74 } /* Literal.String.Other */
.highlight .sr { color: #e6db74 } /* Literal.String.Regex */
.highlight .s1 { color: #e6db74 } /* Literal.String.Single */
.highlight .ss { color: #e6db74 } /* Literal.String.Symbol */
.highlight .bp { color: #f8f8f2 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #a6e22e } /* Name.Function.Magic */
.highlight .vc { color: #f8f8f2 } /* Name.Variable.Class */
.highlight .vg { color: #f8f8f2 } /* Name.Variable.Global */
.highlight .vi { color: #f8f8f2 } /* Name.Variable.Instance */
.highlight .vm { color: #f8f8f2 } /* Name.Variable.Magic */
.highlight .il { color: #ae81ff } /* Literal.Number.Integer.Long */
}
@media (prefers-color-scheme: light) {
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */
.highlight .nl { color: #336699; font-style: italic } /* Name.Label */
.highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */
.highlight .py { color: #336699; font-weight: bold } /* Name.Property */
.highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #336699 } /* Name.Variable */
.highlight .ow { color: #008800 } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */
.highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */
.highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */
.highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */
.highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */
.highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */
.highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */
.highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */
.highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */
.highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */
.highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */
.highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */
.highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */
.highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */
.highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */
.highlight .vc { color: #336699 } /* Name.Variable.Class */
.highlight .vg { color: #dd7700 } /* Name.Variable.Global */
.highlight .vi { color: #3333bb } /* Name.Variable.Instance */
.highlight .vm { color: #336699 } /* Name.Variable.Magic */
.highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */
}
# Copyright (c) 2016-2017 Intel Corporation
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#      http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

---
schema: "yardstick:task:0.1"

scenarios:
-
  type: NSPerf
  traffic_profile: ../../traffic_profiles/prox_binsearch.yaml
  topology: prox-tg-topology-2.yaml

  nodes:
    tg__0: tg_0.yardstick
    vnf__0: vnf_0.yardstick

  options:
    vnf__0:
      collectd:
        interval: 1
      prox_path: /opt/nsb_bin/prox
      prox_config: "configs/handle_l3fwd-2.cfg"
      prox_args:
        "-t": ""
      prox_files:
        "configs/ipv4-2port.lua" : ""
      prox_generate_parameter: True

    tg__0:
      collectd:
        interval: 1
      prox_path: /opt/nsb_bin/prox
      prox_config: "configs/gen_l3fwd-2.cfg"
      prox_args:
        "-e": ""
        "-t": ""

  runner:
    type: Duration
    # we kill after duration, independent of test duration, so set this high
    duration: 1800

context:
  type: Node
  name: yardstick
  nfvi_type: baremetal
  file: prox-baremetal-2.yaml
ref='#n498'>498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045
/*
 * Copyright (C) 2014 Michael Brown <mbrown@fensystems.co.uk>.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301, USA.
 */

FILE_LICENCE ( GPL2_OR_LATER );

#include <string.h>
#include <strings.h>
#include <errno.h>
#include <assert.h>
#include <ctype.h>
#include <ipxe/uaccess.h>
#include <ipxe/deflate.h>

/** @file
 *
 * DEFLATE decompression algorithm
 *
 * This file implements the decompression half of the DEFLATE
 * algorithm specified in RFC 1951.
 *
 * Portions of this code are derived from wimboot's xca.c.
 *
 */

/**
 * Byte reversal table
 *
 * For some insane reason, the DEFLATE format stores some values in
 * bit-reversed order.
 */
static uint8_t deflate_reverse[256];

/** Literal/length base values
 *
 * We include entries only for literal/length codes 257-284.  Code 285
 * does not fit the pattern (it represents a length of 258; following
 * the pattern from the earlier codes would give a length of 259), and
 * has no extra bits.  Codes 286-287 are invalid, but can occur.  We
 * treat any code greater than 284 as meaning "length 285, no extra
 * bits".
 */
static uint8_t deflate_litlen_base[28];

/** Distance base values
 *
 * We include entries for all possible codes 0-31, avoiding the need
 * to check for undefined codes 30 and 31 before performing the
 * lookup.  Codes 30 and 31 are never initialised, and will therefore
 * be treated as meaning "14 extra bits, base distance 0".
 */
static uint16_t deflate_distance_base[32];

/** Code length map */
static uint8_t deflate_codelen_map[19] = {
	16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
};

/** Static Huffman alphabet length patterns */
static struct deflate_static_length_pattern deflate_static_length_patterns[] = {
	/* Literal/length code lengths */
	{ 0x88, ( ( ( 143 -   0 ) + 1 ) / 2 ) },
	{ 0x99, ( ( ( 255 - 144 ) + 1 ) / 2 ) },
	{ 0x77, ( ( ( 279 - 256 ) + 1 ) / 2 ) },
	{ 0x88, ( ( ( 287 - 280 ) + 1 ) / 2 ) },
	/* Distance code lengths */
	{ 0x55, ( ( (  31 -   0 ) + 1 ) / 2 ) },
	/* End marker */
	{ 0, 0 }
};

/**
 * Transcribe binary value (for debugging)
 *
 * @v value		Value
 * @v bits		Length of value (in bits)
 * @ret string		Transcribed value
 */
static const char * deflate_bin ( unsigned long value, unsigned int bits ) {
	static char buf[ ( 8 * sizeof ( value ) ) + 1 /* NUL */ ];
	char *out = buf;

	/* Sanity check */
	assert ( bits < sizeof ( buf ) );

	/* Transcribe value */
	while ( bits-- )
		*(out++) = ( ( value & ( 1 << bits ) ) ? '1' : '0' );
	*out = '\0';

	return buf;
}

/**
 * Set Huffman symbol length
 *
 * @v deflate		Decompressor
 * @v index		Index within lengths
 * @v bits		Symbol length (in bits)
 */
static void deflate_set_length ( struct deflate *deflate, unsigned int index,
				 unsigned int bits ) {

	deflate->lengths[ index / 2 ] |= ( bits << ( 4 * ( index % 2 ) ) );
}

/**
 * Get Huffman symbol length
 *
 * @v deflate		Decompressor
 * @v index		Index within lengths
 * @ret bits		Symbol length (in bits)
 */
static unsigned int deflate_length ( struct deflate *deflate,
				     unsigned int index ) {

	return ( ( deflate->lengths[ index / 2 ] >> ( 4 * ( index % 2 ) ) )
		 & 0x0f );
}

/**
 * Determine Huffman alphabet name (for debugging)
 *
 * @v deflate		Decompressor
 * @v alphabet		Huffman alphabet
 * @ret name		Alphabet name
 */
static const char * deflate_alphabet_name ( struct deflate *deflate,
					    struct deflate_alphabet *alphabet ){

	if ( alphabet == &deflate->litlen ) {
		return "litlen";
	} else if ( alphabet == &deflate->distance_codelen ) {
		return "distance/codelen";
	} else {
		return "<UNKNOWN>";
	}
}

/**
 * Dump Huffman alphabet (for debugging)
 *
 * @v deflate		Decompressor
 * @v alphabet		Huffman alphabet
 */
static void deflate_dump_alphabet ( struct deflate *deflate,
				    struct deflate_alphabet *alphabet ) {
	struct deflate_huf_symbols *huf_sym;
	unsigned int bits;
	unsigned int huf;
	unsigned int i;

	/* Do nothing unless debugging is enabled */
	if ( ! DBG_EXTRA )
		return;

	/* Dump symbol table for each utilised length */
	for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
				   sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
		huf_sym = &alphabet->huf[ bits - 1 ];
		if ( huf_sym->freq == 0 )
			continue;
		huf = ( huf_sym->start >> huf_sym->shift );
		DBGC2 ( alphabet, "DEFLATE %p \"%s\" length %d start \"%s\" "
			"freq %d:", deflate,
			deflate_alphabet_name ( deflate, alphabet ), bits,
			deflate_bin ( huf, huf_sym->bits ), huf_sym->freq );
		for ( i = 0 ; i < huf_sym->freq ; i++ ) {
			DBGC2 ( alphabet, " %03x",
				huf_sym->raw[ huf + i ] );
		}
		DBGC2 ( alphabet, "\n" );
	}

	/* Dump quick lookup table */
	DBGC2 ( alphabet, "DEFLATE %p \"%s\" quick lookup:", deflate,
		deflate_alphabet_name ( deflate, alphabet ) );
	for ( i = 0 ; i < ( sizeof ( alphabet->lookup ) /
			    sizeof ( alphabet->lookup[0] ) ) ; i++ ) {
		DBGC2 ( alphabet, " %d", ( alphabet->lookup[i] + 1 ) );
	}
	DBGC2 ( alphabet, "\n" );
}

/**
 * Construct Huffman alphabet
 *
 * @v deflate		Decompressor
 * @v alphabet		Huffman alphabet
 * @v count		Number of symbols
 * @v offset		Starting offset within length table
 * @ret rc		Return status code
 */
static int deflate_alphabet ( struct deflate *deflate,
			      struct deflate_alphabet *alphabet,
			      unsigned int count, unsigned int offset ) {
	struct deflate_huf_symbols *huf_sym;
	unsigned int huf;
	unsigned int cum_freq;
	unsigned int bits;
	unsigned int raw;
	unsigned int adjustment;
	unsigned int prefix;
	int complete;

	/* Clear symbol table */
	memset ( alphabet->huf, 0, sizeof ( alphabet->huf ) );

	/* Count number of symbols with each Huffman-coded length */
	for ( raw = 0 ; raw < count ; raw++ ) {
		bits = deflate_length ( deflate, ( raw + offset ) );
		if ( bits )
			alphabet->huf[ bits - 1 ].freq++;
	}

	/* Populate Huffman-coded symbol table */
	huf = 0;
	cum_freq = 0;
	for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
				   sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
		huf_sym = &alphabet->huf[ bits - 1 ];
		huf_sym->bits = bits;
		huf_sym->shift = ( 16 - bits );
		huf_sym->start = ( huf << huf_sym->shift );
		huf_sym->raw = &alphabet->raw[cum_freq];
		huf += huf_sym->freq;
		if ( huf > ( 1U << bits ) ) {
			DBGC ( alphabet, "DEFLATE %p \"%s\" has too many "
			       "symbols with lengths <=%d\n", deflate,
			       deflate_alphabet_name ( deflate, alphabet ),
			       bits );
			return -EINVAL;
		}
		huf <<= 1;
		cum_freq += huf_sym->freq;
	}
	complete = ( huf == ( 1U << bits ) );

	/* Populate raw symbol table */
	for ( raw = 0 ; raw < count ; raw++ ) {
		bits = deflate_length ( deflate, ( raw + offset ) );
		if ( bits ) {
			huf_sym = &alphabet->huf[ bits - 1 ];
			*(huf_sym->raw++) = raw;
		}
	}

	/* Adjust Huffman-coded symbol table raw pointers and populate
	 * quick lookup table.
	 */
	for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
				   sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
		huf_sym = &alphabet->huf[ bits - 1 ];

		/* Adjust raw pointer */
		huf_sym->raw -= huf_sym->freq; /* Reset to first symbol */
		adjustment = ( huf_sym->start >> huf_sym->shift );
		huf_sym->raw -= adjustment; /* Adjust for quick indexing */

		/* Populate quick lookup table */
		for ( prefix = ( huf_sym->start >> DEFLATE_HUFFMAN_QL_SHIFT ) ;
		      prefix < ( 1 << DEFLATE_HUFFMAN_QL_BITS ) ; prefix++ ) {
			alphabet->lookup[prefix] = ( bits - 1 );
		}
	}

	/* Dump alphabet (for debugging) */
	deflate_dump_alphabet ( deflate, alphabet );

	/* Check that there are no invalid codes */
	if ( ! complete ) {
		DBGC ( alphabet, "DEFLATE %p \"%s\" is incomplete\n", deflate,
		       deflate_alphabet_name ( deflate, alphabet ) );
		return -EINVAL;
	}

	return 0;
}

/**
 * Attempt to accumulate bits from input stream
 *
 * @v deflate		Decompressor
 * @v in		Compressed input data
 * @v target		Number of bits to accumulate
 * @ret excess		Number of excess bits accumulated (may be negative)
 */
static int deflate_accumulate ( struct deflate *deflate,
				struct deflate_chunk *in,
				unsigned int target ) {
	uint8_t byte;

	while ( deflate->bits < target ) {

		/* Check for end of input */
		if ( in->offset >= in->len )
			break;

		/* Acquire byte from input */
		copy_from_user ( &byte, in->data, in->offset++,
				 sizeof ( byte ) );
		deflate->accumulator = ( deflate->accumulator |
					 ( byte << deflate->bits ) );
		deflate->rotalumucca = ( deflate->rotalumucca |
					 ( deflate_reverse[byte] <<
					   ( 24 - deflate->bits ) ) );
		deflate->bits += 8;

		/* Sanity check */
		assert ( deflate->bits <=
			 ( 8 * sizeof ( deflate->accumulator ) ) );
	}

	return ( deflate->bits - target );
}

/**
 * Consume accumulated bits from the input stream
 *
 * @v deflate		Decompressor
 * @v count		Number of accumulated bits to consume
 * @ret data		Consumed bits
 */
static int deflate_consume ( struct deflate *deflate, unsigned int count ) {
	int data;

	/* Sanity check */
	assert ( count <= deflate->bits );

	/* Extract data and consume bits */
	data = ( deflate->accumulator & ( ( 1 << count ) - 1 ) );
	deflate->accumulator >>= count;
	deflate->rotalumucca <<= count;
	deflate->bits -= count;

	return data;
}

/**
 * Attempt to extract a fixed number of bits from input stream
 *
 * @v deflate		Decompressor
 * @v in		Compressed input data
 * @v target		Number of bits to extract
 * @ret data		Extracted bits (or negative if not yet accumulated)
 */
static int deflate_extract ( struct deflate *deflate, struct deflate_chunk *in,
			     unsigned int target ) {
	int excess;
	int data;

	/* Return immediately if we are attempting to extract zero bits */
	if ( target == 0 )
		return 0;

	/* Attempt to accumulate bits */
	excess = deflate_accumulate ( deflate, in, target );
	if ( excess < 0 )
		return excess;

	/* Extract data and consume bits */
	data = deflate_consume ( deflate, target );
	DBGCP ( deflate, "DEFLATE %p extracted %s = %#x = %d\n", deflate,
		deflate_bin ( data, target ), data, data );

	return data;
}

/**
 * Attempt to decode a Huffman-coded symbol from input stream
 *
 * @v deflate		Decompressor
 * @v in		Compressed input data
 * @v alphabet		Huffman alphabet
 * @ret code		Raw code (or negative if not yet accumulated)
 */
static int deflate_decode ( struct deflate *deflate,
			    struct deflate_chunk *in,
			    struct deflate_alphabet *alphabet ) {
	struct deflate_huf_symbols *huf_sym;
	uint16_t huf;
	unsigned int lookup_index;
	int excess;
	unsigned int raw;

	/* Attempt to accumulate maximum required number of bits.
	 * There may be fewer bits than this remaining in the stream,
	 * even if the stream still contains some complete
	 * Huffman-coded symbols.
	 */
	deflate_accumulate ( deflate, in, DEFLATE_HUFFMAN_BITS );

	/* Normalise the bit-reversed accumulated value to 16 bits */
	huf = ( deflate->rotalumucca >> 16 );

	/* Find symbol set for this length */
	lookup_index = ( huf >> DEFLATE_HUFFMAN_QL_SHIFT );
	huf_sym = &alphabet->huf[ alphabet->lookup[ lookup_index ] ];
	while ( huf < huf_sym->start )
		huf_sym--;

	/* Calculate number of excess bits, and return if not yet complete */
	excess = ( deflate->bits - huf_sym->bits );
	if ( excess < 0 )
		return excess;

	/* Consume bits */
	deflate_consume ( deflate, huf_sym->bits );

	/* Look up raw symbol */
	raw = huf_sym->raw[ huf >> huf_sym->shift ];
	DBGCP ( deflate, "DEFLATE %p decoded %s = %#x = %d\n", deflate,
		deflate_bin ( ( huf >> huf_sym->shift ), huf_sym->bits ),
		raw, raw );

	return raw;
}

/**
 * Discard bits up to the next byte boundary
 *
 * @v deflate		Decompressor
 */
static void deflate_discard_to_byte ( struct deflate *deflate ) {

	deflate_consume ( deflate, ( deflate->bits & 7 ) );
}

/**
 * Copy data to output buffer (if available)
 *
 * @v out		Output data buffer
 * @v start		Source data
 * @v offset		Starting offset within source data
 * @v len		Length to copy
 */
static void deflate_copy ( struct deflate_chunk *out,
			   userptr_t start, size_t offset, size_t len ) {
	size_t out_offset = out->offset;
	size_t copy_len;

	/* Copy data one byte at a time, to allow for overlap */
	if ( out_offset < out->len ) {
		copy_len = ( out->len - out_offset );
		if ( copy_len > len )
			copy_len = len;
		while ( copy_len-- ) {
			memcpy_user ( out->data, out_offset++,
				      start, offset++, 1 );
		}
	}
	out->offset += len;
}

/**
 * Inflate compressed data
 *
 * @v deflate		Decompressor
 * @v in		Compressed input data
 * @v out		Output data buffer
 * @ret rc		Return status code
 *
 * The caller can use deflate_finished() to determine whether a
 * successful return indicates that the decompressor is merely waiting
 * for more input.
 *
 * Data will not be written beyond the specified end of the output
 * data buffer, but the offset within the output data buffer will be
 * updated to reflect the amount that should have been written.  The
 * caller can use this to find the length of the decompressed data
 * before allocating the output data buffer.
 */
int deflate_inflate ( struct deflate *deflate,
		      struct deflate_chunk *in,
		      struct deflate_chunk *out ) {

	/* This could be implemented more neatly if gcc offered a
	 * means for enforcing tail recursion.
	 */
	if ( deflate->resume ) {
		goto *(deflate->resume);
	} else switch ( deflate->format ) {
		case DEFLATE_RAW:	goto block_header;
		case DEFLATE_ZLIB:	goto zlib_header;
		default:		assert ( 0 );
	}

 zlib_header: {
		int header;
		int cm;

		/* Extract header */
		header = deflate_extract ( deflate, in, ZLIB_HEADER_BITS );
		if ( header < 0 ) {
			deflate->resume = &&zlib_header;
			return 0;
		}

		/* Parse header */
		cm = ( ( header >> ZLIB_HEADER_CM_LSB ) & ZLIB_HEADER_CM_MASK );
		if ( cm != ZLIB_HEADER_CM_DEFLATE ) {
			DBGC ( deflate, "DEFLATE %p unsupported ZLIB "
			       "compression method %d\n", deflate, cm );
			return -ENOTSUP;
		}
		if ( header & ( 1 << ZLIB_HEADER_FDICT_BIT ) ) {
			DBGC ( deflate, "DEFLATE %p unsupported ZLIB preset "
			       "dictionary\n", deflate );
			return -ENOTSUP;
		}

		/* Process first block header */
		goto block_header;
	}

 block_header: {
		int header;
		int bfinal;
		int btype;

		/* Extract block header */
		header = deflate_extract ( deflate, in, DEFLATE_HEADER_BITS );
		if ( header < 0 ) {
			deflate->resume = &&block_header;
			return 0;
		}

		/* Parse header */
		deflate->header = header;
		bfinal = ( header & ( 1 << DEFLATE_HEADER_BFINAL_BIT ) );
		btype = ( header >> DEFLATE_HEADER_BTYPE_LSB );
		DBGC ( deflate, "DEFLATE %p found %sblock type %#x\n",
		       deflate, ( bfinal ? "final " : "" ), btype );
		switch ( btype ) {
		case DEFLATE_HEADER_BTYPE_LITERAL:
			goto literal_block;
		case DEFLATE_HEADER_BTYPE_STATIC:
			goto static_block;
		case DEFLATE_HEADER_BTYPE_DYNAMIC:
			goto dynamic_block;
		default:
			DBGC ( deflate, "DEFLATE %p unsupported block type "
			       "%#x\n", deflate, btype );
			return -ENOTSUP;
		}
	}

 literal_block: {

		/* Discard any bits up to the next byte boundary */
		deflate_discard_to_byte ( deflate );
	}

 literal_len: {
		int len;

		/* Extract LEN field */
		len = deflate_extract ( deflate, in, DEFLATE_LITERAL_LEN_BITS );
		if ( len < 0 ) {
			deflate->resume = &&literal_len;
			return 0;
		}

		/* Record length of literal data */
		deflate->remaining = len;
		DBGC2 ( deflate, "DEFLATE %p literal block length %#04zx\n",
			deflate, deflate->remaining );
	}

 literal_nlen: {
		int nlen;

		/* Extract NLEN field */
		nlen = deflate_extract ( deflate, in, DEFLATE_LITERAL_LEN_BITS);
		if ( nlen < 0 ) {
			deflate->resume = &&literal_nlen;
			return 0;
		}

		/* Verify NLEN */
		if ( ( ( deflate->remaining ^ ~nlen ) &
		       ( ( 1 << DEFLATE_LITERAL_LEN_BITS ) - 1 ) ) != 0 ) {
			DBGC ( deflate, "DEFLATE %p invalid len/nlen "
			       "%#04zx/%#04x\n", deflate,
			       deflate->remaining, nlen );
			return -EINVAL;
		}
	}

 literal_data: {
		size_t in_remaining;
		size_t len;

		/* Calculate available amount of literal data */
		in_remaining = ( in->len - in->offset );
		len = deflate->remaining;
		if ( len > in_remaining )
			len = in_remaining;

		/* Copy data to output buffer */
		deflate_copy ( out, in->data, in->offset, len );

		/* Consume data from input buffer */
		in->offset += len;
		deflate->remaining -= len;

		/* Finish processing if we are blocked */
		if ( deflate->remaining ) {
			deflate->resume = &&literal_data;
			return 0;
		}

		/* Otherwise, finish block */
		goto block_done;
	}

 static_block: {
		struct deflate_static_length_pattern *pattern;
		uint8_t *lengths = deflate->lengths;

		/* Construct static Huffman lengths as per RFC 1950 */
		for ( pattern = deflate_static_length_patterns ;
		      pattern->count ; pattern++ ) {
			memset ( lengths, pattern->fill, pattern->count );
			lengths += pattern->count;
		}
		deflate->litlen_count = 288;
		deflate->distance_count = 32;
		goto construct_alphabets;
	}

 dynamic_block:

 dynamic_header: {
		int header;
		unsigned int hlit;
		unsigned int hdist;
		unsigned int hclen;

		/* Extract block header */
		header = deflate_extract ( deflate, in, DEFLATE_DYNAMIC_BITS );
		if ( header < 0 ) {
			deflate->resume = &&dynamic_header;
			return 0;
		}

		/* Parse header */
		hlit = ( ( header >> DEFLATE_DYNAMIC_HLIT_LSB ) &
			 DEFLATE_DYNAMIC_HLIT_MASK );
		hdist = ( ( header >> DEFLATE_DYNAMIC_HDIST_LSB ) &
			  DEFLATE_DYNAMIC_HDIST_MASK );
		hclen = ( ( header >> DEFLATE_DYNAMIC_HCLEN_LSB ) &
			  DEFLATE_DYNAMIC_HCLEN_MASK );
		deflate->litlen_count = ( hlit + 257 );
		deflate->distance_count = ( hdist + 1 );
		deflate->length_index = 0;
		deflate->length_target = ( hclen + 4 );
		DBGC2 ( deflate, "DEFLATE %p dynamic block %d codelen, %d "
			"litlen, %d distance\n", deflate,
			deflate->length_target, deflate->litlen_count,
			deflate->distance_count );

		/* Prepare for decoding code length code lengths */
		memset ( &deflate->lengths, 0, sizeof ( deflate->lengths ) );
	}

 dynamic_codelen: {
		int len;
		unsigned int index;
		int rc;

		/* Extract all code lengths */
		while ( deflate->length_index < deflate->length_target ) {

			/* Extract code length length */
			len = deflate_extract ( deflate, in,
						DEFLATE_CODELEN_BITS );
			if ( len < 0 ) {
				deflate->resume = &&dynamic_codelen;
				return 0;
			}

			/* Store code length */
			index = deflate_codelen_map[deflate->length_index++];
			deflate_set_length ( deflate, index, len );
			DBGCP ( deflate, "DEFLATE %p codelen for %d is %d\n",
				deflate, index, len );
		}

		/* Generate code length alphabet */
		if ( ( rc = deflate_alphabet ( deflate,
					       &deflate->distance_codelen,
					       ( DEFLATE_CODELEN_MAX_CODE + 1 ),
					       0 ) ) != 0 )
			return rc;

		/* Prepare for decoding literal/length/distance code lengths */
		memset ( &deflate->lengths, 0, sizeof ( deflate->lengths ) );
		deflate->length_index = 0;
		deflate->length_target = ( deflate->litlen_count +
					   deflate->distance_count );
		deflate->length = 0;
	}

 dynamic_litlen_distance: {
		int len;
		int index;

		/* Decode literal/length/distance code length */
		len = deflate_decode ( deflate, in, &deflate->distance_codelen);
		if ( len < 0 ) {
			deflate->resume = &&dynamic_litlen_distance;
			return 0;
		}

		/* Prepare for extra bits */
		if ( len < 16 ) {
			deflate->length = len;
			deflate->extra_bits = 0;
			deflate->dup_len = 1;
		} else {
			static const uint8_t dup_len[3] = { 3, 3, 11 };
			static const uint8_t extra_bits[3] = { 2, 3, 7 };
			index = ( len - 16 );
			deflate->dup_len = dup_len[index];
			deflate->extra_bits = extra_bits[index];
			if ( index )
				deflate->length = 0;
		}
	}

 dynamic_litlen_distance_extra: {
		int extra;
		unsigned int dup_len;

		/* Extract extra bits */
		extra = deflate_extract ( deflate, in, deflate->extra_bits );
		if ( extra < 0 ) {
			deflate->resume = &&dynamic_litlen_distance_extra;
			return 0;
		}

		/* Store code lengths */
		dup_len = ( deflate->dup_len + extra );
		while ( ( deflate->length_index < deflate->length_target ) &&
			dup_len-- ) {
			deflate_set_length ( deflate, deflate->length_index++,
					     deflate->length );
		}

		/* Process next literal/length or distance code
		 * length, if more are required.
		 */
		if ( deflate->length_index < deflate->length_target )
			goto dynamic_litlen_distance;

		/* Construct alphabets */
		goto construct_alphabets;
	}

 construct_alphabets: {
		unsigned int distance_offset = deflate->litlen_count;
		unsigned int distance_count = deflate->distance_count;
		int rc;

		/* Generate literal/length alphabet */
		if ( ( rc = deflate_alphabet ( deflate, &deflate->litlen,
					       deflate->litlen_count, 0 ) ) !=0)
			return rc;

		/* Handle degenerate case of a single distance code
		 * (for which it is impossible to construct a valid,
		 * complete Huffman alphabet).  RFC 1951 states:
		 *
		 *   If only one distance code is used, it is encoded
		 *   using one bit, not zero bits; in this case there
		 *   is a single code length of one, with one unused
		 *   code.  One distance code of zero bits means that
		 *   there are no distance codes used at all (the data
		 *   is all literals).
		 *
		 * If we have only a single distance code, then we
		 * instead use two distance codes both with length 1.
		 * This results in a valid Huffman alphabet.  The code
		 * "0" will mean distance code 0 (which is either
		 * correct or irrelevant), and the code "1" will mean
		 * distance code 1 (which is always irrelevant).
		 */
		if ( deflate->distance_count == 1 ) {

			deflate->lengths[0] = 0x11;
			distance_offset = 0;
			distance_count = 2;
		}

		/* Generate distance alphabet */
		if ( ( rc = deflate_alphabet ( deflate,
					       &deflate->distance_codelen,
					       distance_count,
					       distance_offset ) ) != 0 )
			return rc;
	}

 lzhuf_litlen: {
		int code;
		uint8_t byte;
		unsigned int extra;
		unsigned int bits;

		/* Decode Huffman codes */
		while ( 1 ) {

			/* Decode Huffman code */
			code = deflate_decode ( deflate, in, &deflate->litlen );
			if ( code < 0 ) {
				deflate->resume = &&lzhuf_litlen;
				return 0;
			}

			/* Handle according to code type */
			if ( code < DEFLATE_LITLEN_END ) {

				/* Literal value: copy to output buffer */
				byte = code;
				DBGCP ( deflate, "DEFLATE %p literal %#02x "
					"('%c')\n", deflate, byte,
					( isprint ( byte ) ? byte : '.' ) );
				deflate_copy ( out, virt_to_user ( &byte ), 0,
					       sizeof ( byte ) );

			} else if ( code == DEFLATE_LITLEN_END ) {

				/* End of block */
				goto block_done;

			} else {

				/* Length code: process extra bits */
				extra = ( code - DEFLATE_LITLEN_END - 1 );
				if ( extra < 28 ) {
					bits = ( extra / 4 );
					if ( bits )
						bits--;
					deflate->extra_bits = bits;
					deflate->dup_len =
						deflate_litlen_base[extra];
				} else {
					deflate->extra_bits = 0;
					deflate->dup_len = 258;
				}
				goto lzhuf_litlen_extra;
			}
		}
	}

 lzhuf_litlen_extra: {
		int extra;

		/* Extract extra bits */
		extra = deflate_extract ( deflate, in, deflate->extra_bits );
		if ( extra < 0 ) {
			deflate->resume = &&lzhuf_litlen_extra;
			return 0;
		}

		/* Update duplicate length */
		deflate->dup_len += extra;
	}

 lzhuf_distance: {
		int code;
		unsigned int extra;
		unsigned int bits;

		/* Decode Huffman code */
		code = deflate_decode ( deflate, in,
					&deflate->distance_codelen );
		if ( code < 0 ) {
			deflate->resume = &&lzhuf_distance;
			return 0;
		}

		/* Process extra bits */
		extra = code;
		bits = ( extra / 2 );
		if ( bits )
			bits--;
		deflate->extra_bits = bits;
		deflate->dup_distance = deflate_distance_base[extra];
	}

 lzhuf_distance_extra: {
		int extra;
		size_t dup_len;
		size_t dup_distance;

		/* Extract extra bits */
		extra = deflate_extract ( deflate, in, deflate->extra_bits );
		if ( extra < 0 ) {
			deflate->resume = &&lzhuf_distance_extra;
			return 0;
		}

		/* Update duplicate distance */
		dup_distance = ( deflate->dup_distance + extra );
		dup_len = deflate->dup_len;
		DBGCP ( deflate, "DEFLATE %p duplicate length %zd distance "
			"%zd\n", deflate, dup_len, dup_distance );

		/* Sanity check */
		if ( dup_distance > out->offset ) {
			DBGC ( deflate, "DEFLATE %p bad distance %zd (max "
			       "%zd)\n", deflate, dup_distance, out->offset );
			return -EINVAL;
		}

		/* Copy data, allowing for overlap */
		deflate_copy ( out, out->data, ( out->offset - dup_distance ),
			       dup_len );

		/* Process next literal/length symbol */
		goto lzhuf_litlen;
	}

 block_done: {

		DBGCP ( deflate, "DEFLATE %p end of block\n", deflate );

		/* If this was not the final block, process next block header */
		if ( ! ( deflate->header & ( 1 << DEFLATE_HEADER_BFINAL_BIT ) ))
			goto block_header;

		/* Otherwise, process footer (if any) */
		switch ( deflate->format ) {
		case DEFLATE_RAW:	goto finished;
		case DEFLATE_ZLIB:	goto zlib_footer;
		default:		assert ( 0 );
		}
	}

 zlib_footer: {

		/* Discard any bits up to the next byte boundary */
		deflate_discard_to_byte ( deflate );
	}

 zlib_adler32: {
		int excess;

		/* Accumulate the 32 bits of checksum.  We don't check
		 * the value, stop processing immediately afterwards,
		 * and so don't have to worry about the nasty corner
		 * cases involved in calling deflate_extract() to
		 * obtain a full 32 bits.
		 */
		excess = deflate_accumulate ( deflate, in, ZLIB_ADLER32_BITS );
		if ( excess < 0 ) {
			deflate->resume = &&zlib_adler32;
			return 0;
		}

		/* Finish processing */
		goto finished;
	}

 finished: {
		/* Mark as finished and terminate */
		DBGCP ( deflate, "DEFLATE %p finished\n", deflate );
		deflate->resume = NULL;
		return 0;
	}
}

/**
 * Initialise decompressor
 *
 * @v deflate		Decompressor
 * @v format		Compression format code
 */
void deflate_init ( struct deflate *deflate, enum deflate_format format ) {
	static int global_init_done;
	uint8_t i;
	uint8_t bit;
	uint8_t byte;
	unsigned int base;
	unsigned int bits;

	/* Perform global initialisation if required */
	if ( ! global_init_done ) {

		/* Initialise byte reversal table */
		for ( i = 255 ; i ; i-- ) {
			for ( bit = 1, byte = 0 ; bit ; bit <<= 1 ) {
				byte <<= 1;
				if ( i & bit )
					byte |= 1;
			}
			deflate_reverse[i] = byte;
		}

		/* Initialise literal/length extra bits table */
		base = 3;
		for ( i = 0 ; i < 28 ; i++ ) {
			bits = ( i / 4 );
			if ( bits )
				bits--;
			deflate_litlen_base[i] = base;
			base += ( 1 << bits );
		}
		assert ( base == 259 ); /* sic */

		/* Initialise distance extra bits table */
		base = 1;
		for ( i = 0 ; i < 30 ; i++ ) {
			bits = ( i / 2 );
			if ( bits )
				bits--;
			deflate_distance_base[i] = base;
			base += ( 1 << bits );
		}
		assert ( base == 32769 );

		/* Record global initialisation as complete */
		global_init_done = 1;
	}

	/* Initialise structure */
	memset ( deflate, 0, sizeof ( *deflate ) );
	deflate->format = format;
}