编程介的小学生 2019-05-11 09:37 采纳率: 20.5%
浏览 233

十六进制数据的分析的一个问题,怎么采用C程序的代码的编写技术思想去实现呢?

Problem Description
Protocol Buffers are a way of encoding structured data in an efficient yet extensible format. Google uses Protocol Buffers for almost all of its internal RPC protocols and file formats. In this problem, you will use a simplified version of protocol buffers.

Message definition:
In protocol buffers, we defining a message in a very simple way:
message Gao {
required int32 a = 1;
required int32 b = 2;
required string str = 3;
repeated int32 arr = 4;
optional int32 optionalField = 5;
}
The Gao message definition specifies five fields (name/value pairs), one for each piece of data that you want to include in this type of message. In this problem, there are at most 15 fields in one message definition.

Field definition:
Foremost, we need specifying field rules in one of the following:
1. required: message must have exactly one of this field.
2. optional: message can have zero or one of this field (but not more than one).
3. repeated: this field can be repeated any number of times (including zero) in message. The order of the repeated values will be preserved.
Follow by the field rules, we definiting field by type and name. we support int32 and string type in this problem. Each field has assigned a unique numbered tag at the end. These tags are used to identify your fields in the message binary format. The smallest tag number is 1, and the largest is 15. Field name is consist of letters([a-zA-Z]) and do not exceed 15 characters.

Base 128 Varints:
To understand your simple protocol buffer encoding, you first need to understand varints. Varints are a method of serializing integers using one or more bytes. Smaller numbers take a smaller number of bytes. Each byte in a varint, except the last byte, has the most significant bit (msb) set –– this indicates that there are further bytes to come. The lower 7 bits of each byte are used to store the two's complement representation of the number in groups of 7 bits, least significant group first.
So, for example, here is the number 1 –– it's a single byte, so the msb is not set:
0000 0001
And here is 300 – this is a bit more complicated:
1010 1100 0000 0010
How do you figure out that this is 300? First you drop the msb from each byte, as this is just there to tell us whether we've reached the end of the number (as you can see, it's set in the first byte as there is more than one byte in the varint):
1010 1100 0000 0010
→ 010 1100 000 0010
You reverse the two groups of 7 bits because, as you remember, varints store numbers with the least significant group first. Then you concatenate them to get your final value:
000 0010 010 1100
→ 000 0010 ++ 010 1100
→ 100101100
→ 256 + 32 + 8 + 4 = 300
(++ means byte concatenation)
It's more complex to consider signed number, due to simplify this problem, we only need considered unsigned integers in range [0, 10^9].

Message structure:
As you know, a protocol buffer message is a series of key-value pairs. The binary version of a message just uses the field's tag number as the key –– the name and declared type for each field can only be determined on the decoding end by referencing the message type's definition. The "key" for each pair in a wire-format message is actually two values – the field tag number from your message definition, plus a wire type that provides just enough information to find the length of the following value.
The available wire types are as follows:
Type Meaning Used for
0 Varint int32
2 Length-delimited string,repeated fields
Each key in the streamed message is a varint with the value (field_tag_number << 3) | wire_type –– in other words, the last three bits of the number store the wire type. For example, key of field a in message Gao is encoded as 0000 1000(08), and for field str is 0001 1010(1A). Field a seted as 150 will be encoded as 08 96 01 (Key is 08 and 150 encoded as 96 01). Concatenate all encoded fields we can get the encoded message.

Optional Elements:
If any of fields are optional, the encoded message may not have a key-value pair with that field, in this situation, just set the value of this field as null.

String and Repeated Elements:
In this situation, we need specifiy payload size (varint type) first after key, and followed by the elements. (We can regard string type as a array)
For example:
message Test3 {
required string b = 2;
repeated int32 c = 3;
}
Assume one message have the value "testing" for the field b and the values 3, 270, and 86942 for the repeated field c, then, the encoded form would be:
12 // tag (field number 2, wire type 2)
07 // payload size (7 bytes)
74 65 73 74 69 6E 67 // ascii code of "testing"
1A // tag (field number 3, wire type 2)
06 // payload size (6 bytes)
03 // first element (varint 3)
8E 02 // second element (varint 270)
9E A7 05 // third element (varint 86942)
Notice, repeated string type in this problem is illegal.
If any of repetead fields not appeared in this message, this field can regard as empty array([]).
The length of arrays and strings will not exceed 50 and strings only consist of alphabet('a' - 'z' and 'A' - 'Z').

Problem:
Now give you a message definition, and serval encoded messages, you task is decode this messages.

Input
The first line of input contains a number T, indicating the number of test cases. (T≤10).

For each case, there will be two integers n (n≤17) and m (m≤100).

The next n lines consist of message definition, you can assume that the length of message definition will not exceed 1500. A valid definition will only contains alphabet('a' - 'z' and 'A' - 'Z'), number('0' - '9'), whitespace(' ') and control tokens('=;{}').

And then followed by m querys, each line contain one encoded byte stream in hexadecimal notation, there is one whitespace after each byte. And for there are at most 1500 bytes each message. Notice there will be some empty byte stream in test data, see sample input for more details.

All the messages in this problem will not contains unknown tags and have a illegal structure.

Output
For each case, output Case #i: first. (i is the number of the test case, from 1 to T).

Then for each query, output the values in each fields, with the same order in message definition.

If any of required fields not appeared in this message, please print Error! instead.

Output a blank line after each query.

Sample Input
1
2 5
message Test1{required int32 a=1;required string b=2
;repeated int32 c=3;optional int32 optionalField=5;}
08 96 01 12 07 74 65 73 74 69 6e 67 1A 06 03 8E 02 9E A7 05 28 00
08 96 01 12 07 74 65 73 74 69 6e 67 1A 06 03 8E 02 9E A7 05

08 96 01 12 01 74
12 07 74 65 73 74 69 6e 67 1A 06 03 8E 02 9E A7 05

Sample Output
Case #1:
a = 150
b = "testing"
c = [3, 270, 86942]
optionalField = 0

a = 150
b = "testing"
c = [3, 270, 86942]
optionalField = null

Error!

a = 150
b = "t"
c = []
optionalField = null

Error!

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 matlab数字图像处理频率域滤波
    • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
    • ¥15 ELGamal和paillier计算效率谁快?
    • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
    • ¥15 ubuntu系统下挂载磁盘上执行./提示权限不够
    • ¥15 Arcgis相交分析无法绘制一个或多个图形
    • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
    • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
    • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
    • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误