[Dwarf-discuss] Clarification: DW_OP_mod doesn't specify which definition of modulo
Ben Woodard
woodard@redhat.com
Thu Sep 25 01:03:02 GMT 2025
On 9/24/25 4:46 PM, Ron Brender wrote:
> For starters, the proposed text is a non-starter (forgive the play on
> words)
> because there is no Chapter 2 Section 4 in Knuth's The Art of Computer
> Programming Volume 1. Chapter 2 is entitled Information Structures, in
> which
> section 2.4 (is that what you mean by "Section 4"?) is entitled
> Multilinked
> Structures, and has nothing to do with the modulo operation.
>
> The discussion mentions Section 1.2.4, which is actually in Volume 1,
> Chapter 1, is entitled Integer Functions and Elementary Number Theory,
> and does define and discuss the modulo operation.
I can correct that. When we were discussing the issue, Cary pulled out
his copy Knuth, mine is tucked away in a box that never got unpacked the
last time that I moved. I misunderstood his citation.
>
> Even if the citation were correct, I would object on the grounds that
> I believe
> the DWARF text should provide the definition, not a citation that the
> reader
> needs to consult. A footnote to an external source might be OK if
> there were
> complicated issues of possible supplementary interest.
I was kind of hoping that the dwarf-discuss community could propose what
they think it should be and then I'll be happy to write that into the
text of the proposal. I really don't have a strong opinion on the matter.
I just think that whatever the algorithm is, it should be in the
standard. Right now we have:
1) GDB implmenting, Knuth's algorithm but limited to signed and unsigned
integers.
2) IIUC John DelSignore said TotalView implements DW_OP_mod using C's %
operator.
3) and we have an email from Michael Eager from 2011 saying that
DW_OP_mod should only apply to unsigned integral types.
Let's all just get on the same page. (I don't care what page it is.)
>
> Finally, the Knuth definition is given in terms of real numbers, of which
> integers are a special case, using floor and ceiling operations. This
> would be appropriate if DWARF DW_OP_mod were intended to apply
> to floating-point operands but is rather pedantic overkill for just
> integers.
Yeah but in that section we have two broad classes of operators
arithmetic and logical. All the other arithmetic operators are defined
with a domain that includes non-integral types. Should we exclude this
one arithmetic operator from that more expansive range?
It is not as if the algorithm is unknown or particularly complicated.
/x/ mod /y/ = /x/ − /y/ × floor(/x/ / /y/), if /y/ ≠ 0; /x/ mod 0 = /x/.
>
> But I think the real problem is not the definition of DW_OP_mod per se but
> the definition of the generic type. DWARF Section 2.5.2 defines the
> generic
> type as an "integral type that has the size of an address on the
> target machine
> and unspecified signedness." We know that some architectures treat
> addresses
> as signed and some as unsigned integers, and DWARF is trying not to care.
>
> Most of the time it mostly doesn't matter. But to be concrete, what
> does one make of
>
> DW_OP_lit5
> DW_OP_lit2
> DW_OP_neg
> DW_OP_mod
>
> If the generic type is signed, then the result is -1. However, if the
> generic type
> is thought to be unsigned, then "-2" is just a very large positive
> number and
> the result is 5.
>
exactly!
> We might think about solving this problem by defining the generic type
> to be
> a) signed
> b) unsigned
> c) signedness implementation-defined
> I would not advocate either a) or b). Moreover, I would be very
> caution in overturning the
> "non-signedness" of generic type which has been characteristic of
> DWARF from the beginning
> (even before the name "generic type" was introduced).
I am either too young or have lived a too sheltered life to be aware of
any architectures which actually have signed addressing. I've seen
plenty of cases where there are signed offsets added to unsigned
addresses to make unsigned addresses. This address arithmetic avoids the
complication of mixed signed and unsigned arithmetic which can slip into
naively written C code.
It seems to me that what you are really wanting with the generic type is
"address arithmetic" where you can do "unsigned_address + signed_offset"
and not have to worry about the C rules that can cause mixed unsigned
and signed arithmetic to yield unexpected results. For example I believe
that "unsigned_address + signed_offset" is actually defined to be
"unsigned_address + (unsigned) signed_offset" causing a a very large
unsigned value to be added to the unsigned address in the case where
signed_offset happens to be a small negative.
I think that both "signed" and "unsigned" are kind of C concepts and I
would suggest that an other option which may provide a way out of this
dilemma is:
d) the generic type is a type is defined to be an integral type suitable
for address arithmetic.
and more specifically this means that when implementing a consumer in C
you must be careful when mixing signed and unsigned values doing
something like:
if (signed_offset >=0 )
unsigned_address+=signed_offset;
else
unsigned_address-=abs(signed_offset);
There may be other cases where the arithmetic of the "generic type"
diverges from integers in C or other language in subtle ways. DW_OP_mod
may be one of those but I haven't thought about it enough to be sure.
-ben
>
> Defining DW_OP_mod to be defined only for unsigned integers seems
> overkill and unnecessary when no generic type operands are involved.
>
> A more permissive approach is to specify that an operand of the generic
> type is implicitly treated as unsigned. Then use the Knuth definition
> restricted to
> integers. This is close to Ben's second alternative but further
> resolves the ambiguity
> of generic signedness.
>
> Ben has raised a definite problem for which further thought is surely
> warranted...
>
> Ron
>
>
>
>
>
>
> On Wed, Sep 24, 2025 at 2:32 PM Ben Woodard via Dwarf-discuss
> <dwarf-discuss@lists.dwarfstd.org> wrote:
>
> Background:
>
> Evidently, originally DWARF didn't allow arithmetic operations on
> floating point numbers and most uses of the DWARF stack were done
> with
> the assumption that the values being acted upon were addresses and so
> the computation was assumed to be acting upon unsigned numbers.
>
> At some point, DWARF began to allow the arithmetic operations to
> work on
> floating point numbers and several operations were explicitly
> defined to
> work over non-integral values. This led to the paragraph in the
> current
> DWARF working draft that says in section 2.5.2.4 on page 37 lines
> 24-27:
>
> "Operations other than DW_OP_abs, DW_OP_div, DW_OP_minus,
> DW_OP_mul, DW_OP_neg and DW_OP_plus require integral types of the
> operand (either integral base type or the generic type).
> Operations do
> not cause
> an exception on overflow."
>
> Unlike all the other arithmetic operations this explicitly limits
> DW_OP_mod to integral base types and the generic type. It lumps
> DW_OP_mod in with the logical operations. Furthermore, there are
> multiple definitions of the modulo operator which vary in how they
> handle signed values.
>
> According to the dwarf-discuss archives, this issue came up back
> in 2011
> and at that time Michael Eager made a pronouncement that DW_OP_mod
> used
> the modulo algorithm for unsigned arithmetic. However, this
> decision was
> not recorded in the standard. Since that time, consumers have
> implemented different implementations of DW_OP_mod.
>
> This proposal seeks to clarify and harmonize the consumer
> implementations of the DW_OP_mod operator by defining which
> algorithm to
> use for signed arithmetic as well as define it for floating point
> numbers.
>
> Proposal:
>
> Add DW_OP_mod to the list of operators which do not require integral
> base types by changing:
>
> Operations other than DW_OP_abs, DW_OP_div, DW_OP_minus, DW_OP_mul,
> DW_OP_neg and DW_OP_plus require integral types of the operand
> (either
> integral base type or the generic type).
>
> To:
>
> Operations other than DW_OP_abs, DW_OP_div, DW_OP_mod, DW_OP_minus,
> DW_OP_mul, DW_OP_neg and DW_OP_plus require integral types of the
> operand (either integral base type or the generic type).
>
> Then append the following sentence to the description of the
> DW_OP_mod:
>
> The algorithm used to implement modulo shall be the one defined in
> The
> Art of Computer Programming Volume 1: Fundamental Algorithms
> Chapter 2
> Section 4. Knuth.
>
> Alternative proposals:
>
> 1) Explicitly state in the standard that DW_OP_mod is only defined
> for
> unsigned integral arithmetic. This effectively standardizes the
> Michael
> Eager's pronouncement from 2011.
>
> 2) Pick any algorithm for modulo that works for signed as well
> unsigned
> arithmetic and specify that DW_OP_modulo shall follow it. The current
> GDB implementation follows Knuth 1.2.4 for signed and unsigned
> integral
> arithmetic but excludes the algorithm for reals and floating point
> numbers.
>
>
> --
> Dwarf-discuss mailing list
> Dwarf-discuss@lists.dwarfstd.org
> https://lists.dwarfstd.org/mailman/listinfo/dwarf-discuss
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.dwarfstd.org/pipermail/dwarf-discuss/attachments/20250924/1219b9bc/attachment.htm>
More information about the Dwarf-discuss
mailing list