View Javadoc
1   /*
2    * Copyright 2015 The Netty Project
3    *
4    * The Netty Project licenses this file to you under the Apache License,
5    * version 2.0 (the "License"); you may not use this file except in compliance
6    * with the License. You may obtain a copy of the License at:
7    *
8    *   https://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12   * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13   * License for the specific language governing permissions and limitations
14   * under the License.
15   */
16  
17  /*
18   * Copyright 2014 Twitter, Inc.
19   *
20   * Licensed under the Apache License, Version 2.0 (the "License");
21   * you may not use this file except in compliance with the License.
22   * You may obtain a copy of the License at
23   *
24   *     https://www.apache.org/licenses/LICENSE-2.0
25   *
26   * Unless required by applicable law or agreed to in writing, software
27   * distributed under the License is distributed on an "AS IS" BASIS,
28   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
29   * See the License for the specific language governing permissions and
30   * limitations under the License.
31   */
32  package io.netty.handler.codec.http2;
33  
34  import io.netty.handler.codec.http.HttpHeaderNames;
35  import io.netty.handler.codec.http.HttpMethod;
36  import io.netty.handler.codec.http.HttpResponseStatus;
37  import io.netty.handler.codec.http2.Http2Headers.PseudoHeaderName;
38  import io.netty.util.AsciiString;
39  import io.netty.util.internal.PlatformDependent;
40  
41  import java.util.Arrays;
42  import java.util.List;
43  
44  import static io.netty.handler.codec.http2.HpackUtil.equalsVariableTime;
45  
46  final class HpackStaticTable {
47  
48      static final int NOT_FOUND = -1;
49  
50      // Appendix A: Static Table
51      // https://tools.ietf.org/html/rfc7541#appendix-A
52      private static final List<HpackHeaderField> STATIC_TABLE = Arrays.asList(
53      /*  1 */ newEmptyPseudoHeaderField(PseudoHeaderName.AUTHORITY),
54      /*  2 */ newPseudoHeaderMethodField(HttpMethod.GET),
55      /*  3 */ newPseudoHeaderMethodField(HttpMethod.POST),
56      /*  4 */ newPseudoHeaderField(PseudoHeaderName.PATH, "/"),
57      /*  5 */ newPseudoHeaderField(PseudoHeaderName.PATH, "/index.html"),
58      /*  6 */ newPseudoHeaderField(PseudoHeaderName.SCHEME, "http"),
59      /*  7 */ newPseudoHeaderField(PseudoHeaderName.SCHEME, "https"),
60      /*  8 */ newPseudoHeaderField(PseudoHeaderName.STATUS, HttpResponseStatus.OK.codeAsText()),
61      /*  9 */ newPseudoHeaderField(PseudoHeaderName.STATUS, HttpResponseStatus.NO_CONTENT.codeAsText()),
62      /* 10 */ newPseudoHeaderField(PseudoHeaderName.STATUS, HttpResponseStatus.PARTIAL_CONTENT.codeAsText()),
63      /* 11 */ newPseudoHeaderField(PseudoHeaderName.STATUS, HttpResponseStatus.NOT_MODIFIED.codeAsText()),
64      /* 12 */ newPseudoHeaderField(PseudoHeaderName.STATUS, HttpResponseStatus.BAD_REQUEST.codeAsText()),
65      /* 13 */ newPseudoHeaderField(PseudoHeaderName.STATUS, HttpResponseStatus.NOT_FOUND.codeAsText()),
66      /* 14 */ newPseudoHeaderField(PseudoHeaderName.STATUS, HttpResponseStatus.INTERNAL_SERVER_ERROR.codeAsText()),
67      /* 15 */ newEmptyHeaderField(HttpHeaderNames.ACCEPT_CHARSET),
68      /* 16 */ newHeaderField(HttpHeaderNames.ACCEPT_ENCODING, "gzip, deflate"),
69      /* 17 */ newEmptyHeaderField(HttpHeaderNames.ACCEPT_LANGUAGE),
70      /* 18 */ newEmptyHeaderField(HttpHeaderNames.ACCEPT_RANGES),
71      /* 19 */ newEmptyHeaderField(HttpHeaderNames.ACCEPT),
72      /* 20 */ newEmptyHeaderField(HttpHeaderNames.ACCESS_CONTROL_ALLOW_ORIGIN),
73      /* 21 */ newEmptyHeaderField(HttpHeaderNames.AGE),
74      /* 22 */ newEmptyHeaderField(HttpHeaderNames.ALLOW),
75      /* 23 */ newEmptyHeaderField(HttpHeaderNames.AUTHORIZATION),
76      /* 24 */ newEmptyHeaderField(HttpHeaderNames.CACHE_CONTROL),
77      /* 25 */ newEmptyHeaderField(HttpHeaderNames.CONTENT_DISPOSITION),
78      /* 26 */ newEmptyHeaderField(HttpHeaderNames.CONTENT_ENCODING),
79      /* 27 */ newEmptyHeaderField(HttpHeaderNames.CONTENT_LANGUAGE),
80      /* 28 */ newEmptyHeaderField(HttpHeaderNames.CONTENT_LENGTH),
81      /* 29 */ newEmptyHeaderField(HttpHeaderNames.CONTENT_LOCATION),
82      /* 30 */ newEmptyHeaderField(HttpHeaderNames.CONTENT_RANGE),
83      /* 31 */ newEmptyHeaderField(HttpHeaderNames.CONTENT_TYPE),
84      /* 32 */ newEmptyHeaderField(HttpHeaderNames.COOKIE),
85      /* 33 */ newEmptyHeaderField(HttpHeaderNames.DATE),
86      /* 34 */ newEmptyHeaderField(HttpHeaderNames.ETAG),
87      /* 35 */ newEmptyHeaderField(HttpHeaderNames.EXPECT),
88      /* 36 */ newEmptyHeaderField(HttpHeaderNames.EXPIRES),
89      /* 37 */ newEmptyHeaderField(HttpHeaderNames.FROM),
90      /* 38 */ newEmptyHeaderField(HttpHeaderNames.HOST),
91      /* 39 */ newEmptyHeaderField(HttpHeaderNames.IF_MATCH),
92      /* 40 */ newEmptyHeaderField(HttpHeaderNames.IF_MODIFIED_SINCE),
93      /* 41 */ newEmptyHeaderField(HttpHeaderNames.IF_NONE_MATCH),
94      /* 42 */ newEmptyHeaderField(HttpHeaderNames.IF_RANGE),
95      /* 43 */ newEmptyHeaderField(HttpHeaderNames.IF_UNMODIFIED_SINCE),
96      /* 44 */ newEmptyHeaderField(HttpHeaderNames.LAST_MODIFIED),
97      /* 45 */ newEmptyHeaderField("link"),
98      /* 46 */ newEmptyHeaderField(HttpHeaderNames.LOCATION),
99      /* 47 */ newEmptyHeaderField(HttpHeaderNames.MAX_FORWARDS),
100     /* 48 */ newEmptyHeaderField(HttpHeaderNames.PROXY_AUTHENTICATE),
101     /* 49 */ newEmptyHeaderField(HttpHeaderNames.PROXY_AUTHORIZATION),
102     /* 50 */ newEmptyHeaderField(HttpHeaderNames.RANGE),
103     /* 51 */ newEmptyHeaderField(HttpHeaderNames.REFERER),
104     /* 52 */ newEmptyHeaderField("refresh"),
105     /* 53 */ newEmptyHeaderField(HttpHeaderNames.RETRY_AFTER),
106     /* 54 */ newEmptyHeaderField(HttpHeaderNames.SERVER),
107     /* 55 */ newEmptyHeaderField(HttpHeaderNames.SET_COOKIE),
108     /* 56 */ newEmptyHeaderField("strict-transport-security"),
109     /* 57 */ newEmptyHeaderField(HttpHeaderNames.TRANSFER_ENCODING),
110     /* 58 */ newEmptyHeaderField(HttpHeaderNames.USER_AGENT),
111     /* 59 */ newEmptyHeaderField(HttpHeaderNames.VARY),
112     /* 60 */ newEmptyHeaderField(HttpHeaderNames.VIA),
113     /* 61 */ newEmptyHeaderField(HttpHeaderNames.WWW_AUTHENTICATE)
114     );
115 
116     private static HpackHeaderField newEmptyHeaderField(AsciiString name) {
117         return new HpackHeaderField(name, AsciiString.EMPTY_STRING);
118     }
119 
120     private static HpackHeaderField newEmptyHeaderField(String name) {
121         return new HpackHeaderField(AsciiString.cached(name), AsciiString.EMPTY_STRING);
122     }
123 
124     private static HpackHeaderField newHeaderField(AsciiString name, String value) {
125         return new HpackHeaderField(name, AsciiString.cached(value));
126     }
127 
128     private static HpackHeaderField newPseudoHeaderMethodField(HttpMethod method) {
129         return new HpackHeaderField(PseudoHeaderName.METHOD.value(), method.asciiName());
130     }
131 
132     private static HpackHeaderField newPseudoHeaderField(PseudoHeaderName name, AsciiString value) {
133         return new HpackHeaderField(name.value(), value);
134     }
135 
136     private static HpackHeaderField newPseudoHeaderField(PseudoHeaderName name, String value) {
137         return new HpackHeaderField(name.value(), AsciiString.cached(value));
138     }
139 
140     private static HpackHeaderField newEmptyPseudoHeaderField(PseudoHeaderName name) {
141         return new HpackHeaderField(name.value(), AsciiString.EMPTY_STRING);
142     }
143 
144     // The table size and bit shift are chosen so that each hash bucket contains a single header name.
145     private static final int HEADER_NAMES_TABLE_SIZE = 1 << 9;
146 
147     private static final int HEADER_NAMES_TABLE_SHIFT = PlatformDependent.BIG_ENDIAN_NATIVE_ORDER ? 22 : 18;
148 
149     // A table mapping header names to their associated indexes.
150     private static final HeaderNameIndex[] HEADER_NAMES = new HeaderNameIndex[HEADER_NAMES_TABLE_SIZE];
151     static {
152         // Iterate through the static table in reverse order to
153         // save the smallest index for a given name in the table.
154         for (int index = STATIC_TABLE.size(); index > 0; index--) {
155             HpackHeaderField entry = getEntry(index);
156             int bucket = headerNameBucket(entry.name);
157             HeaderNameIndex tableEntry = HEADER_NAMES[bucket];
158             if (tableEntry != null && !equalsVariableTime(tableEntry.name, entry.name)) {
159                 // Can happen if AsciiString.hashCode changes
160                 throw new IllegalStateException("Hash bucket collision between " +
161                   tableEntry.name + " and " + entry.name);
162             }
163             HEADER_NAMES[bucket] = new HeaderNameIndex(entry.name, index, entry.value.length() == 0);
164         }
165     }
166 
167     // The table size and bit shift are chosen so that each hash bucket contains a single header.
168     private static final int HEADERS_WITH_NON_EMPTY_VALUES_TABLE_SIZE = 1 << 6;
169 
170     private static final int HEADERS_WITH_NON_EMPTY_VALUES_TABLE_SHIFT =
171       PlatformDependent.BIG_ENDIAN_NATIVE_ORDER ? 0 : 6;
172 
173     // A table mapping headers with non-empty values to their associated indexes.
174     private static final HeaderIndex[] HEADERS_WITH_NON_EMPTY_VALUES =
175       new HeaderIndex[HEADERS_WITH_NON_EMPTY_VALUES_TABLE_SIZE];
176     static {
177         for (int index = STATIC_TABLE.size(); index > 0; index--) {
178             HpackHeaderField entry = getEntry(index);
179             if (entry.value.length() > 0) {
180                 int bucket = headerBucket(entry.value);
181                 HeaderIndex tableEntry = HEADERS_WITH_NON_EMPTY_VALUES[bucket];
182                 if (tableEntry != null) {
183                     // Can happen if AsciiString.hashCode changes
184                     throw new IllegalStateException("Hash bucket collision between " +
185                       tableEntry.value + " and " + entry.value);
186                 }
187                 HEADERS_WITH_NON_EMPTY_VALUES[bucket] = new HeaderIndex(entry.name, entry.value, index);
188             }
189         }
190     }
191 
192     /**
193      * The number of header fields in the static table.
194      */
195     static final int length = STATIC_TABLE.size();
196 
197     /**
198      * Return the header field at the given index value.
199      */
200     static HpackHeaderField getEntry(int index) {
201         return STATIC_TABLE.get(index - 1);
202     }
203 
204     /**
205      * Returns the lowest index value for the given header field name in the static table. Returns
206      * -1 if the header field name is not in the static table.
207      */
208     static int getIndex(CharSequence name) {
209         HeaderNameIndex entry = getEntry(name);
210         return entry == null ? NOT_FOUND : entry.index;
211     }
212 
213     /**
214      * Returns the index value for the given header field in the static table. Returns -1 if the
215      * header field is not in the static table.
216      */
217     static int getIndexInsensitive(CharSequence name, CharSequence value) {
218         if (value.length() == 0) {
219             HeaderNameIndex entry = getEntry(name);
220             return entry == null || !entry.emptyValue ? NOT_FOUND : entry.index;
221         }
222         int bucket = headerBucket(value);
223         HeaderIndex header = HEADERS_WITH_NON_EMPTY_VALUES[bucket];
224         if (header == null) {
225             return NOT_FOUND;
226         }
227         if (equalsVariableTime(header.name, name) && equalsVariableTime(header.value, value)) {
228             return header.index;
229         }
230         return NOT_FOUND;
231     }
232 
233     private static HeaderNameIndex getEntry(CharSequence name) {
234         int bucket = headerNameBucket(name);
235         HeaderNameIndex entry = HEADER_NAMES[bucket];
236         if (entry == null) {
237             return null;
238         }
239         return equalsVariableTime(entry.name, name) ? entry : null;
240     }
241 
242     private static int headerNameBucket(CharSequence name) {
243         return bucket(name, HEADER_NAMES_TABLE_SHIFT, HEADER_NAMES_TABLE_SIZE - 1);
244     }
245 
246     private static int headerBucket(CharSequence value) {
247         return bucket(value, HEADERS_WITH_NON_EMPTY_VALUES_TABLE_SHIFT, HEADERS_WITH_NON_EMPTY_VALUES_TABLE_SIZE - 1);
248     }
249 
250     private static int bucket(CharSequence s, int shift, int mask) {
251         return (AsciiString.hashCode(s) >> shift) & mask;
252     }
253 
254     private static final class HeaderNameIndex {
255         final CharSequence name;
256         final int index;
257         final boolean emptyValue;
258 
259         HeaderNameIndex(CharSequence name, int index, boolean emptyValue) {
260             this.name = name;
261             this.index = index;
262             this.emptyValue = emptyValue;
263         }
264     }
265 
266     private static final class HeaderIndex {
267         final CharSequence name;
268         final CharSequence value;
269         final int index;
270 
271         HeaderIndex(CharSequence name, CharSequence value, int index) {
272             this.name = name;
273             this.value = value;
274             this.index = index;
275         }
276     }
277 
278     // singleton
279     private HpackStaticTable() {
280     }
281 }