G1.8.2 Count the UTF-8 Bytes

EasyImplementIcarus · browser samples / server checksReview the topic

Read the leading bits of a UTF-8 byte. Tell the length of a character, a continuation byte, or a byte that never appears.

Hardware context: The grant logger of an eight-way arbiter and the cursor logic of a UTF-8 serial terminal. Classify every UTF-8 byte as a first byte with its length, a continuation byte or a byte that is never used.

A serial terminal receives text as UTF-8 bytes. To move its cursor one character at a time, it must know how many bytes each character takes. The answer is in the leading bits of the first byte.

This is an Implement problem. Write utf8_lead. For a first byte, len is the length of its character and the two flags are 0. A continuation byte sets cont, and a byte that is never used sets bad. In both of those cases len is 0.

The check applies sixteen bytes, one per nanosecond, and records the three outputs after each. Between them the cases try every byte value.

Signals in the Timeline

SignalWidthRole
script128input of each check
Full specification
The module (keep the name and the ports)
module utf8_lead (
  input  logic [7:0] b,      // one byte of a UTF-8 stream
  output logic [2:0] len,    // bytes in the character that b starts: 1 to 4, or 0
  output logic       cont,   // 1 when b is a continuation byte
  output logic       bad     // 1 when b can never appear: 11111xxx
);
  // your design
endmodule
blencontbad
0xxxxxxx100
10xxxxxx010
110xxxxx200
1110xxxx300
11110xxx400
11111xxx001

Judge each byte by its leading bits alone, as in the table. Some other bytes are also forbidden in real UTF-8, such as c0; this block does not check that.

The result fields are len_step0, cont_step0 and bad_step0 for the first byte, up to the same names with step15.

Examples

Example 1

Bytes 00 to 0f
Input
b 00; b 01; b 02; b 03; b 04; b 05; b 06; b 07; b 08; b 09; b 0a; b 0b; b 0c; b 0d; b 0e; b 0f
Output
len_step0 = 1, cont_step0 = no, bad_step0 = no, len_step1 = 1, cont_step1 = no, bad_step1 = no, len_step2 = 1, cont_step2 = no, bad_step2 = no, len_step3 = 1, cont_step3 = no, bad_step3 = no, len_step4 = 1, cont_step4 = no, bad_step4 = no, len_step5 = 1, cont_step5 = no, bad_step5 = no, len_step6 = 1, cont_step6 = no, bad_step6 = no, len_step7 = 1, cont_step7 = no, bad_step7 = no, len_step8 = 1, cont_step8 = no, bad_step8 = no, len_step9 = 1, cont_step9 = no, bad_step9 = no, len_step10 = 1, cont_step10 = no, bad_step10 = no, len_step11 = 1, cont_step11 = no, bad_step11 = no, len_step12 = 1, cont_step12 = no, bad_step12 = no, len_step13 = 1, cont_step13 = no, bad_step13 = no, len_step14 = 1, cont_step14 = no, bad_step14 = no, len_step15 = 1, cont_step15 = no, bad_step15 = no

Every byte here starts with 0, so each is a one-byte character: len is 1 and both flags are 0.

Example 2

Bytes 80 to 8f
Input
b 80; b 81; b 82; b 83; b 84; b 85; b 86; b 87; b 88; b 89; b 8a; b 8b; b 8c; b 8d; b 8e; b 8f
Output
len_step0 = 0, cont_step0 = yes, bad_step0 = no, len_step1 = 0, cont_step1 = yes, bad_step1 = no, len_step2 = 0, cont_step2 = yes, bad_step2 = no, len_step3 = 0, cont_step3 = yes, bad_step3 = no, len_step4 = 0, cont_step4 = yes, bad_step4 = no, len_step5 = 0, cont_step5 = yes, bad_step5 = no, len_step6 = 0, cont_step6 = yes, bad_step6 = no, len_step7 = 0, cont_step7 = yes, bad_step7 = no, len_step8 = 0, cont_step8 = yes, bad_step8 = no, len_step9 = 0, cont_step9 = yes, bad_step9 = no, len_step10 = 0, cont_step10 = yes, bad_step10 = no, len_step11 = 0, cont_step11 = yes, bad_step11 = no, len_step12 = 0, cont_step12 = yes, bad_step12 = no, len_step13 = 0, cont_step13 = yes, bad_step13 = no, len_step14 = 0, cont_step14 = yes, bad_step14 = no, len_step15 = 0, cont_step15 = yes, bad_step15 = no

Every byte here starts with 10. Each is a continuation byte: len is 0 and cont is 1.

Example 3

Bytes c0 to Cf
Input
b c0; b c1; b c2; b c3; b c4; b c5; b c6; b c7; b c8; b c9; b ca; b cb; b cc; b cd; b ce; b cf
Output
len_step0 = 2, cont_step0 = no, bad_step0 = no, len_step1 = 2, cont_step1 = no, bad_step1 = no, len_step2 = 2, cont_step2 = no, bad_step2 = no, len_step3 = 2, cont_step3 = no, bad_step3 = no, len_step4 = 2, cont_step4 = no, bad_step4 = no, len_step5 = 2, cont_step5 = no, bad_step5 = no, len_step6 = 2, cont_step6 = no, bad_step6 = no, len_step7 = 2, cont_step7 = no, bad_step7 = no, len_step8 = 2, cont_step8 = no, bad_step8 = no, len_step9 = 2, cont_step9 = no, bad_step9 = no, len_step10 = 2, cont_step10 = no, bad_step10 = no, len_step11 = 2, cont_step11 = no, bad_step11 = no, len_step12 = 2, cont_step12 = no, bad_step12 = no, len_step13 = 2, cont_step13 = no, bad_step13 = no, len_step14 = 2, cont_step14 = no, bad_step14 = no, len_step15 = 2, cont_step15 = no, bad_step15 = no

Every byte here starts with 110, the first byte of a 2-byte character: len is 2 and both flags are 0.

Constraints and Contract

  • Inputs are known 0/1 values. Each byte is held for one nanosecond and the outputs are sampled at its end.
  • Keep the module name and the ports. The design is combinational.

Hints

Hint 1

Count the 1s at the top of the byte, before the first 0.

Hint 2

No leading 1 is an ASCII byte. Exactly one is a continuation byte. Two, three or four is the length of a character.

Hint 3

A casez with ? for the bits that do not matter writes the table almost as it stands.

What the grader checks: Sixteen cases of sixteen bytes cover all 256 byte values, and two more cases run real text and every prefix boundary. All three outputs are compared after every byte with a model written in JavaScript.

18 checks on Icarus · browser samples / server checks. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.

See all 3 steps and the final capstone

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

Bytes 00 to 0f

Input
b 00; b 01; b 02; b 03; b 04; b 05; b 06; b 07; b 08; b 09; b 0a; b 0b; b 0c; b 0d; b 0e; b 0f
Expected output
len_step0 = 1, cont_step0 = no, bad_step0 = no, len_step1 = 1, cont_step1 = no, bad_step1 = no, len_step2 = 1, cont_step2 = no, bad_step2 = no, len_step3 = 1, cont_step3 = no, bad_step3 = no, len_step4 = 1, cont_step4 = no, bad_step4 = no, len_step5 = 1, cont_step5 = no, bad_step5 = no, len_step6 = 1, cont_step6 = no, bad_step6 = no, len_step7 = 1, cont_step7 = no, bad_step7 = no, len_step8 = 1, cont_step8 = no, bad_step8 = no, len_step9 = 1, cont_step9 = no, bad_step9 = no, len_step10 = 1, cont_step10 = no, bad_step10 = no, len_step11 = 1, cont_step11 = no, bad_step11 = no, len_step12 = 1, cont_step12 = no, bad_step12 = no, len_step13 = 1, cont_step13 = no, bad_step13 = no, len_step14 = 1, cont_step14 = no, bad_step14 = no, len_step15 = 1, cont_step15 = no, bad_step15 = no

Every byte here starts with 0, so each is a one-byte character: len is 1 and both flags are 0.

Run samples executes all 3 public checks. Check all tests runs 18 checks on the server.

Icarus · browser samples / server checks