# PrismParser: A Framework for Implementing Efficient P4-Programmable Packet Parsers on FPGA
## 3 Proposed P4-Programmable Parser
### Software Overview
#### 3.1.2 P4 Compiled JSON File  
The most important fields within the JSON file are _header types_, _headers_, and _parsers_. The _header types_ array defines the types of each header, where each object includes field names, lengths, and an ID number, referred to as the protocol ID in this paper. The headers array maps each header type to its respective header. The most crucial part of the P4 compiled JSON file is the parser array. Typically, each object in this array represents a parsing state based on the current parsed header, its transition key (the fields of interest for parsing in the header), and transitions (which detail the next parsing state based on the value of each transition key). Therefore, parsing can be conceptualized as a directed acyclic graph (DAG), where each node symbolizes a header, and the edges denote transitions between headers based on the transition key and its value. Listing 1 shows a simplified P4 compiled JSON file, which shows the header types, headers, and parsers for the Ethernet header:  
```
1{
2\"header_types\":[{
3\"name\":\"etherent_t\",
4\"id\":1,
5\"fields\":[
6\"dstAddr\",48],
7\"srcAddr\",48],
8[\"etherType\",16]
9]
10]
11\"headers\":[{
12\"name\":\"etherent\",
13\"header_type\":\"etherent_t\"
14],
15]
16\"parsers\":[{
17\"name\":\"parse_etherent\",
18\"transition_key\":[{
19\"type\":\"field\",
20\"value\":[\"ethereType\"]
21}],
22\"transitions\":[
23\"value\":\"0x0800\",\"next_state\":\"parse_ipv4\"),
24{\"value\":\"0x1800\",\"next_state\":\"parse_inner_vlan\"},
25{\"value\":\"0x9100\",\"next_state\":\"parse_outer_vlan\"},
26{\"value\":\"0x66D0\",\"next_state\":\"parse_ipv6\"}
27]]
28]

Figure 2: Proposed compilation workflow for generating control and configuration for the parser. #### 3.1.3 Hardware Configuration Generation

JSON processing and DAG generation are implemented using Python. The initial step involves extracting the required information from the JSON file, including header size, transition key lengths, and their locations relative to the start of the header, protocol ID, and transitions. This is achieved by matching the header types with the header arrays and looking for parser transition key field information within them. Based on this information, the DAG is generated. Subsequently, all simple paths from the root to the leaves of the DAG are found using a Depth-First Search (DFS) algorithm. Some paths to the leaf nodes are discarded since the last headers do not need to be considered parsing states. Now, for these paths and the extracted information from the JSON file, the following hardware configurations are generated per each path:

* 1_. Bitmap length is equal to the number of parsable headers. * **Protocol mask**: Determined by the transition key length and position within a 16-bit long chunk per each header in the path. * **Match values and next state**: Determined by the extracted transitions per each header in the path. * **Multiplexer select lines and enable signals**: Determined by the bus size, number of inputs per each mux, and transition key location. * **Next state bitmap**: The OR value of the header protocol and next header bitmaps. For example, for the Ethernet header, these contents are generated:
* **Protocol bitmap**: \"_00000001_\"; consider that there are seven headers and _protocol_ID_ is 1. * **Protocol mask**: 0x\"FFFF\", since the transition key _etherType_ is 16 bits long. * **Match values and next state**: Match value vector is 0x\"08008100910086 DD_\" which is the concatenated transitions values. The next state is 0x\"4325\", which is _protocol_ID_ for each match, meaning that when _etherType_ = 0x\"9100\", the next parser state will be _protocol_ID_ 2, which is _parse_outer_ylan_ in our example. * 1 signifies that this specific protocol can occur in that clock cycle. The select vector determines the selection of one of the four inputs of a multiplexer for an activated protocol. With two bits to select the binary range of _\"00\"_ to _\"11\"_, one of the four inputs of the multiplexer is chosen.