Electrical – Verilog modulus operator for wrapping around a range

hdlsystem-verilogverilog

My background is in software and I'm new to (System)Verilog so when tasked with implementing a caesar shifter (shift each letter in a string by N letters, wrapping around if necessary e.g. ABCXYZ shifted by 3 becomes DEFABC), I wrote the following, hoping to be able to reduce code duplication, like I would in software:

  /* every variable except 'direction' has the type 'byte' */
  always_comb
  begin
    shifted_char = fresh_char; /* don't touch bytes that aren't letters */
    is_lower_case = "z" >= fresh_char && fresh_char >= "a";
    is_upper_case = "Z" >= fresh_char && fresh_char >= "A";
    if (is_lower_case || is_upper_case)
      begin
        unique if (is_lower_case)
          alphabet_start = "a";
        else if (is_upper_case)
          alphabet_start = "A";
        alphabet_position = fresh_char - alphabet_start;
        if (direction == "f") /* direction is a module parameter: f for forwards results in a shifter, any other value results in an 'unshifter' */
          new_alphabet_position = (26 + (alphabet_position + shift_by)) % 26;
        else
          new_alphabet_position = (26 + (alphabet_position - shift_by)) % 26;
        shifted_char = new_alphabet_position + alphabet_start;
      end
  end

My question is (assuming it's a forward shifter): regarding the "% 26" part, can I expect the synthesizer to deduce that the range of possible values it's going to get at that point is [26, 26+25+25] ([26, 76]) and so there's only 2 cases the logic needs to distinguish between (>26 and >52), rather than [whatever is the smart call when having handle all possible 256 different inputs – (would it be to consider the cases >26, >52, >78 etc…? Or is there a better way? I digress…)]?

I could always do the following:

new_alphabet_position = alphabet_position + shift_by;
if (new_alphabet_position > 25)
  new_alpahbet_position -= 26;

/* Or, for the reverse shifter: */

new_alphabet_position = alphabet_position - shift_by;
if (new_alphabet_position < 0)
  new_alpahbet_position += 26;

…but was curious and wanted to ask that, as well as a related one (that I expect more people will be able to answer): Can it be used to make a normal non-power-of-2 counter (e.g.
count <= (count + 1) % 6;
)? Going by hgleamon1's response to the following thread, it seems as though (at least one) VHDL synth tool might interpret it as intended: https://forums.xilinx.com/t5/Synthesis/Modulus-synthesizable-or-non-synthesizable/td-p/747493

Best Answer

Unless there is a specialized macro cell, non powers of 2 modulus will take a large number of gates and have relatively long propagation delays especially if done as pure combiantional logic.

Be aware depending on your synthesizer the variables 'alphabet_start', 'alphabet_position', and 'new_alphabet_position' my be inferred latches. The way you used them is as intermediated logic, so if you don't references them outside this always block and your synthesizer has decent optimization, then it will not be a latch. To guarantee they will not be latches, they must be given default values outside the if statement.

You state that all variables except 'direction' are type 'byte', this means 'shift_by' may have a value greater than 25 or less than -25 ('byte' is a signed value by default). By using a signed values and adding three value (26 + (alphabet_position + shift_by)) before using the modulus, there is a decent changes that the mod26 will be evaluated on a 10-bit signed value. That will use more logic than if used on an 8-bit value. There is a change your synthesizer may do some optimization, but it might not be great.

If you can guarantee 'shift_by' is less than 26 and greater than -26 ( greater or equal to 0 if unsigned), then you don't need 'alphabet_position' or 'new_alphabet_position'. Simply add or subtract the 'shift_by' and calculate if out of range. For the range check, fist check if 8'(shifted_char-26) >= alphabet_start. The reason for this is to make sure we are comparing positive numbers. "z"+25 is 147 which is negative for a signed 8-bit value. The 8'() with cast it as an 8-bit unsigned value to trim any non-zero intermediate 9th+ bit(s). If an adjustment is not needed then check if hifted_char < alphabet_start as now the possibility of overflowing to a negative number has been already handled.

If you cannot guarantee 'shift_by' is within range, then you have no choose by to mod it. Luckily this is an 8-bit signed value which is better than your original worse case with a 10-bit signed value. This is not ideal but the best I can offer. It is more optimal to have the driver of 'shift_by' assign a legal value then adding more logic to mod it.

Since you are using SystemVerilog, you may want to consider using fresh_char inside { ["A":"Z"] } which is functionally the same as "Z" >= fresh_char && fresh_char >= "A". The inside is keyword is intended to be synthesizable, but I don't know if it is commonly supported.

Consider the following code. It may not be the most optimized, but it is more optimized than your original code:

always_comb
begin
  shift_by_mod26 = shift_by % 26; // %26 is not need if guaranteed asb(value) < 26
  alphabet_start = (fresh_char inside { ["A":"Z"] }) ? "A" : "a";
  if ( fresh_char inside { ["A":"Z"], ["a":"z"] } )
  begin
     if (direction == "f")
       shifted_char = fresh_char + shift_by_mod26;
     else
       shifted_char = fresh_char - shift_by_mod26;

     // subtract 26 first in case shifted_char is >127
     // bring back to a positive if signed (>127 unsigned is negative signed)
     if (8'(shifted_char-26) >= alphabet_start)
       shifted_char -= 26;
     else if (shifted_char < alphabet_start)
       shifted_char += 26;
  end
  else
  begin
    /* don't touch bytes that aren't letters */
    shifted_char = fresh_char;
  end
end

Note: if 'direction' is not a type 'byte', then it must be at least a 7bits(unsigned) wide or greater (sign agnostic) to every match "f"

Cross post answer for a cross post question

Related Topic