← Back to branch summary

~hamo/ubuntu/precise/grub2/grub2.hi_res

« back to all changes in this revision

Viewing changes to grub-core/lib/xzembed/xz_lzma2.h

  • Committer: Bazaar Package Importer
  • Author(s): Colin Watson, Colin Watson, Evan Broder, Mario Limonciello
  • Date: 2010-11-24 13:59:55 UTC
  • mfrom: (1.17.6 upstream) (17.6.15 experimental)
  • Revision ID: james.westby@ubuntu.com-20101124135955-r6ii5sepayr7jt53
Tags: 1.99~20101124-1ubuntu1
https://launchpad.net/bugs/677758
[ Colin Watson ]
* Resynchronise with Debian experimental.  Remaining changes:
  - Adjust for default Ubuntu boot options ("quiet splash").
  - Default to hiding the menu; holding down Shift at boot will show it.
  - Set a monochromatic theme for Ubuntu.
  - Apply Ubuntu GRUB Legacy changes to legacy update-grub script: title,
    recovery mode, quiet option, tweak how memtest86+ is displayed, and
    use UUIDs where appropriate.
  - Fix backslash-escaping in merge_debconf_into_conf.
  - Remove "GNU/Linux" from default distributor string.
  - Add crashkernel= options if kdump and makedumpfile are available.
  - If other operating systems are installed, then automatically unhide
    the menu.  Otherwise, if GRUB_HIDDEN_TIMEOUT is 0, then use keystatus
    if available to check whether Shift is pressed.  If it is, show the
    menu, otherwise boot immediately.  If keystatus is not available, then
    fall back to a short delay interruptible with Escape.
  - Allow Shift to interrupt 'sleep --interruptible'.
  - Don't display introductory message about line editing unless we're
    actually offering a shell prompt.  Don't clear the screen just before
    booting if we never drew the menu in the first place.
  - Remove some verbose messages printed before reading the configuration
    file.
  - Suppress progress messages as the kernel and initrd load for
    non-recovery kernel menu entries.
  - Change prepare_grub_to_access_device to handle filesystems
    loop-mounted on file images.
  - Ignore devices loop-mounted from files in 10_linux.
  - Show the boot menu if the previous boot failed, that is if it failed
    to get to the end of one of the normal runlevels.
  - Don't generate /boot/grub/device.map during grub-install or
    grub-mkconfig by default.
  - Adjust upgrade version checks for Ubuntu.
  - Don't display "GRUB loading" unless Shift is held down.
  - Adjust versions of grub-doc and grub-legacy-doc conflicts to tolerate
    our backport of the grub-doc split.
  - Fix LVM/RAID probing in the absence of /boot/grub/device.map.
  - Look for .mo files in /usr/share/locale-langpack as well, in
    preference.
  - Make sure GRUB_TIMEOUT isn't quoted unnecessarily.
  - Probe all devices in 'grub-probe --target=drive' if
    /boot/grub/device.map is missing.
  - Build-depend on qemu-kvm rather than qemu-system for grub-pc tests.
  - Use qemu rather than qemu-system-i386.
  - Program vesafb on BIOS systems rather than efifb.
  - Add a grub-rescue-efi-amd64 package containing a rescue CD-ROM image
    for EFI-AMD64.
  - On Wubi, don't ask for an install device, but just update wubildr
    using the diverted grub-install.
  - When embedding the core image in a post-MBR gap, check for and avoid
    sectors matching any of a list of known signatures.
  - Disable video_bochs and video_cirrus on PC BIOS systems, as probing
    PCI space seems to break on some systems.
* Downgrade "ACPI shutdown failed" error to a debug message, since it can
  cause spurious test failures.

[ Evan Broder ]
* Enable lua from grub-extras.
* Incorporate the bitop library into lua.
* Add enum_pci function to grub module in lua.
* Switch back to gfxpayload=keep by default, unless the video hardware
  is known to not support it.

[ Mario Limonciello ]
* Built part_msdos and vfat into bootx64.efi (LP: #677758)

Show diffs side-by-side

added added

removed removed

Lines of Context:
grub-core/lib/xzembed/xz_lzma2.h
 
1
/* xz_lzma2.h - LZMA2 definitions */
 
2
/*
 
3
 *  GRUB  --  GRand Unified Bootloader
 
4
 *  Copyright (C) 2010  Free Software Foundation, Inc.
 
5
 *
 
6
 *  GRUB is free software: you can redistribute it and/or modify
 
7
 *  it under the terms of the GNU General Public License as published by
 
8
 *  the Free Software Foundation, either version 3 of the License, or
 
9
 *  (at your option) any later version.
 
10
 *
 
11
 *  GRUB is distributed in the hope that it will be useful,
 
12
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
13
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
14
 *  GNU General Public License for more details.
 
15
 *
 
16
 *  You should have received a copy of the GNU General Public License
 
17
 *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
 
18
 */
 
19
/*
 
20
 * This file is based on code from XZ embedded project
 
21
 * http://tukaani.org/xz/embedded.html
 
22
 */
 
23
 
 
24
#ifndef XZ_LZMA2_H
 
25
#define XZ_LZMA2_H
 
26
 
 
27
/* dictionary size hard limit
 
28
 * actual size limit is calculated as shown in 5.3.1
 
29
 * http://tukaani.org/xz/xz-file-format.txt
 
30
 *
 
31
 * if bits > 39 dictionary_size = UINT32_MAX
 
32
 * else
 
33
 * dictionary_size = 2 | (bits & 1);
 
34
 * dictionary_size <<= bits / 2 + 11;
 
35
 *
 
36
 * i.e.
 
37
 * 0  - 4 KiB
 
38
 * 6  - 32 KiB
 
39
 * 30 - 128MiB
 
40
 * 39 - 3072 MiB
 
41
 * 40 - 4096 MiB - 1 B
 
42
 * note: implementation supports 39 at maximum
 
43
 */
 
44
#define DICT_BIT_SIZE 30
 
45
 
 
46
/* Range coder constants */
 
47
#define RC_SHIFT_BITS 8
 
48
#define RC_TOP_BITS 24
 
49
#define RC_TOP_VALUE (1 << RC_TOP_BITS)
 
50
#define RC_BIT_MODEL_TOTAL_BITS 11
 
51
#define RC_BIT_MODEL_TOTAL (1 << RC_BIT_MODEL_TOTAL_BITS)
 
52
#define RC_MOVE_BITS 5
 
53
 
 
54
/*
 
55
 * Maximum number of position states. A position state is the lowest pb
 
56
 * number of bits of the current uncompressed offset. In some places there
 
57
 * are different sets of probabilities for different position states.
 
58
 */
 
59
#define POS_STATES_MAX (1 << 4)
 
60
 
 
61
/*
 
62
 * This enum is used to track which LZMA symbols have occurred most recently
 
63
 * and in which order. This information is used to predict the next symbol.
 
64
 *
 
65
 * Symbols:
 
66
 *  - Literal: One 8-bit byte
 
67
 *  - Match: Repeat a chunk of data at some distance
 
68
 *  - Long repeat: Multi-byte match at a recently seen distance
 
69
 *  - Short repeat: One-byte repeat at a recently seen distance
 
70
 *
 
71
 * The symbol names are in from STATE_oldest_older_previous. REP means
 
72
 * either short or long repeated match, and NONLIT means any non-literal.
 
73
 */
 
74
enum lzma_state {
 
75
        STATE_LIT_LIT,
 
76
        STATE_MATCH_LIT_LIT,
 
77
        STATE_REP_LIT_LIT,
 
78
        STATE_SHORTREP_LIT_LIT,
 
79
        STATE_MATCH_LIT,
 
80
        STATE_REP_LIT,
 
81
        STATE_SHORTREP_LIT,
 
82
        STATE_LIT_MATCH,
 
83
        STATE_LIT_LONGREP,
 
84
        STATE_LIT_SHORTREP,
 
85
        STATE_NONLIT_MATCH,
 
86
        STATE_NONLIT_REP
 
87
};
 
88
 
 
89
/* Total number of states */
 
90
#define STATES 12
 
91
 
 
92
/* The lowest 7 states indicate that the previous state was a literal. */
 
93
#define LIT_STATES 7
 
94
 
 
95
/* Indicate that the latest symbol was a literal. */
 
96
static inline void lzma_state_literal(enum lzma_state *state)
 
97
{
 
98
        if (*state <= STATE_SHORTREP_LIT_LIT)
 
99
                *state = STATE_LIT_LIT;
 
100
        else if (*state <= STATE_LIT_SHORTREP)
 
101
                *state -= 3;
 
102
        else
 
103
                *state -= 6;
 
104
}
 
105
 
 
106
/* Indicate that the latest symbol was a match. */
 
107
static inline void lzma_state_match(enum lzma_state *state)
 
108
{
 
109
        *state = *state < LIT_STATES ? STATE_LIT_MATCH : STATE_NONLIT_MATCH;
 
110
}
 
111
 
 
112
/* Indicate that the latest state was a long repeated match. */
 
113
static inline void lzma_state_long_rep(enum lzma_state *state)
 
114
{
 
115
        *state = *state < LIT_STATES ? STATE_LIT_LONGREP : STATE_NONLIT_REP;
 
116
}
 
117
 
 
118
/* Indicate that the latest symbol was a short match. */
 
119
static inline void lzma_state_short_rep(enum lzma_state *state)
 
120
{
 
121
        *state = *state < LIT_STATES ? STATE_LIT_SHORTREP : STATE_NONLIT_REP;
 
122
}
 
123
 
 
124
/* Test if the previous symbol was a literal. */
 
125
static inline bool lzma_state_is_literal(enum lzma_state state)
 
126
{
 
127
        return state < LIT_STATES;
 
128
}
 
129
 
 
130
/* Each literal coder is divided in three sections:
 
131
 *   - 0x001-0x0FF: Without match byte
 
132
 *   - 0x101-0x1FF: With match byte; match bit is 0
 
133
 *   - 0x201-0x2FF: With match byte; match bit is 1
 
134
 *
 
135
 * Match byte is used when the previous LZMA symbol was something else than
 
136
 * a literal (that is, it was some kind of match).
 
137
 */
 
138
#define LITERAL_CODER_SIZE 0x300
 
139
 
 
140
/* Maximum number of literal coders */
 
141
#define LITERAL_CODERS_MAX (1 << 4)
 
142
 
 
143
/* Minimum length of a match is two bytes. */
 
144
#define MATCH_LEN_MIN 2
 
145
 
 
146
/* Match length is encoded with 4, 5, or 10 bits.
 
147
 *
 
148
 * Length   Bits
 
149
 *  2-9      4 = Choice=0 + 3 bits
 
150
 * 10-17     5 = Choice=1 + Choice2=0 + 3 bits
 
151
 * 18-273   10 = Choice=1 + Choice2=1 + 8 bits
 
152
 */
 
153
#define LEN_LOW_BITS 3
 
154
#define LEN_LOW_SYMBOLS (1 << LEN_LOW_BITS)
 
155
#define LEN_MID_BITS 3
 
156
#define LEN_MID_SYMBOLS (1 << LEN_MID_BITS)
 
157
#define LEN_HIGH_BITS 8
 
158
#define LEN_HIGH_SYMBOLS (1 << LEN_HIGH_BITS)
 
159
#define LEN_SYMBOLS (LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS + LEN_HIGH_SYMBOLS)
 
160
 
 
161
/*
 
162
 * Maximum length of a match is 273 which is a result of the encoding
 
163
 * described above.
 
164
 */
 
165
#define MATCH_LEN_MAX (MATCH_LEN_MIN + LEN_SYMBOLS - 1)
 
166
 
 
167
/*
 
168
 * Different sets of probabilities are used for match distances that have
 
169
 * very short match length: Lengths of 2, 3, and 4 bytes have a separate
 
170
 * set of probabilities for each length. The matches with longer length
 
171
 * use a shared set of probabilities.
 
172
 */
 
173
#define DIST_STATES 4
 
174
 
 
175
/*
 
176
 * Get the index of the appropriate probability array for decoding
 
177
 * the distance slot.
 
178
 */
 
179
static inline uint32_t lzma_get_dist_state(uint32_t len)
 
180
{
 
181
        return len < DIST_STATES + MATCH_LEN_MIN
 
182
                        ? len - MATCH_LEN_MIN : DIST_STATES - 1;
 
183
}
 
184
 
 
185
/*
 
186
 * The highest two bits of a 32-bit match distance are encoded using six bits.
 
187
 * This six-bit value is called a distance slot. This way encoding a 32-bit
 
188
 * value takes 6-36 bits, larger values taking more bits.
 
189
 */
 
190
#define DIST_SLOT_BITS 6
 
191
#define DIST_SLOTS (1 << DIST_SLOT_BITS)
 
192
 
 
193
/* Match distances up to 127 are fully encoded using probabilities. Since
 
194
 * the highest two bits (distance slot) are always encoded using six bits,
 
195
 * the distances 0-3 don't need any additional bits to encode, since the
 
196
 * distance slot itself is the same as the actual distance. DIST_MODEL_START
 
197
 * indicates the first distance slot where at least one additional bit is
 
198
 * needed.
 
199
 */
 
200
#define DIST_MODEL_START 4
 
201
 
 
202
/*
 
203
 * Match distances greater than 127 are encoded in three pieces:
 
204
 *   - distance slot: the highest two bits
 
205
 *   - direct bits: 2-26 bits below the highest two bits
 
206
 *   - alignment bits: four lowest bits
 
207
 *
 
208
 * Direct bits don't use any probabilities.
 
209
 *
 
210
 * The distance slot value of 14 is for distances 128-191.
 
211
 */
 
212
#define DIST_MODEL_END 14
 
213
 
 
214
/* Distance slots that indicate a distance <= 127. */
 
215
#define FULL_DISTANCES_BITS (DIST_MODEL_END / 2)
 
216
#define FULL_DISTANCES (1 << FULL_DISTANCES_BITS)
 
217
 
 
218
/*
 
219
 * For match distances greater than 127, only the highest two bits and the
 
220
 * lowest four bits (alignment) is encoded using probabilities.
 
221
 */
 
222
#define ALIGN_BITS 4
 
223
#define ALIGN_SIZE (1 << ALIGN_BITS)
 
224
#define ALIGN_MASK (ALIGN_SIZE - 1)
 
225
 
 
226
/* Total number of all probability variables */
 
227
#define PROBS_TOTAL (1846 + LITERAL_CODERS_MAX * LITERAL_CODER_SIZE)
 
228
 
 
229
/*
 
230
 * LZMA remembers the four most recent match distances. Reusing these
 
231
 * distances tends to take less space than re-encoding the actual
 
232
 * distance value.
 
233
 */
 
234
#define REPS 4
 
235
 
 
236
#endif