Within the C committee, there’s been a lot of talk about what the C charter means and whether it should be updated or not. My personal musing on the topic is that the C charter needs to be updated in … Continue reading →
Within the C committee, there’s been a lot of talk about what the C charter means and whether it should be updated or not. My personal musing on the topic is that the C charter needs to be updated in order for C to remain relevant long-term. Whether C should remain relevant long-term is an exercise left to the reader. Note, these thoughts may change over time as I gather more feedback from more places. Existing code is important, existing implementations are not. A standard is a treaty between implementor and programmer. Migration of an existing code base is an issue. Minimize incompatibilities with C90. I think we could combine these principles into one bullet instead of four because they’re all effectively about code migration to newer standard versions. Each new release of C should provide a simple upgrade path from the previous release of C so that users can gradually transition between adjacent versions of C, but incompatibilities between releases are acceptable. In other words, it’s fine to deprecate old functionality even without replacement, or remove previously deprecated functionality (again, even without replacement), but this should only be done with significant justification given the costs to users of C. Changing the standard a code base compiles against is a new agreement between the programmer and the implementer; it is akin to changing your code (as is changing your compiler), and there should be no expectation that everything remains identical to how it was before. Older functionality will be deprecated, newer functionality will be added, bugs will be fixed, etc. New standard == new treaty. I think we should be careful about blind adherence to this principle. It’s obviously true that there’s a lot of economic value tied up in existing C code bases and that rewriting that code is both expensive and error-prone. However, C has undergone multiple revisions in its long history. A good idea in 1978 is not necessarily even acceptable practice in 2024. I would love to see this principle updated to set a time limit, along the lines of: existing code that has been maintained to not use features marked deprecated, obsolescent, or removed in the past ten years is important; unmaintained code and existing implementations are not. If you cannot update your code to stop relying on deprecated functionality, your code is not actually economically important — people spend time and money maintaining things that are economically important. C code can be portable. C code can be non-portable. I think both of these principles are still reasonable today. While commodity hardware has trended towards more homogeneity, there is still plenty of heterogeneous hardware solutions out there (DSPs, FPGAs, etc) and domains like AI, ML, cryptography, etc are pushing the boundaries for new hardware solutions. We should continue to aim to be as portable as possible while not constraining ourselves to the lowest common denominator of hardware. Avoid quiet changes. I still strongly believe in this principle. It directly impacts transitions between standard versions — quiet changes make it much harder for users to upgrade to the latest standard. Keep the spirit of C. I do not think this principle has much value because it is too subjective, though I understand the desire behind it. I think people want C to remain familiar between releases instead of being reinvented. For example, I think users do not want to see a Perl 5/Perl 6- or Python 2/Python 3-style bifurcation of the language and community. However, I think the principle that existing code is important is sufficient to cover that need. Most especially, I think concepts like “trust the programmer”, “don’t prevent the programmer from doing what needs to be done”, “make it fast”, etc are problematic given the increased need for improved security in system’s level programming languages. I would prefer to see this bullet removed because it’s not an actionable principle and I think other bullets cover the main thrust of what it was trying to say. Support international programming. I still strongly believe in this principle, though I worry that WG14 lacks enough expertise to really help validate designs in this space. I appreciate that WG21’s SG16 members have been willing to provide advice, and that the Unicode consortium folks are actively engaging with programming language committees as well. But there’s more to internationalization than simply text (for example, units of measure, date/time functionality, and input methods are also part of internationalization). I think the goal is excellent, but hopefully we have enough humility as a committee to recognize when we could use outside advice. Codify existing practice to address evident deficiencies. Unlike for C99, the consensus at the London meeting was that there should be no invention, without exception. I think these bullets are saying the same thing and we only need to say this once if we wish to say it at all. However, I do not think the committee agrees with the idea of no invention without exception and we do everyone a disservice by stating it as a principle. For starters, we’ve shown we’re perfectly comfortable with invention during the C11 and C23 cycles. Invention is necessary if we want to unify divergent existing practice in the wild into something standardized. “No new invention” is why we still have no solution for a “pointer + size” type or a “string” type. There are a lot of different ways to solve those kinds of problems and until the committee picks one and says “This is The Way”, we’ll continue to see more ad hoc solutions. That said, I think there are really important points hiding in these two bullets. For example, having a principled way to separate “need” from “want” is critical to avoid spending too much committee time on work that does not benefit enough users. What makes something a good feature to standardize vs not? How integrated should a feature be (for example, does adding a new arithmetic type to the language also require it be supported in I/O operations in the standard library, etc)? When two implementations support the same notional feature with slightly differing semantics, should the committee use undefined behavior to resolve the conflict so no users have to change code, or should the committee push for well-defined behavior despite knowing it will break some users? I think we want to have answers to these sorts of questions, but they’re less about charter and more about feature design guidance. Perhaps we want a second document to help authors understand what the committee needs in a proposal and why? Minimize incompatibilities with C++ C++ inherits the C standard library almost directly from C, but the core C++ language is specified entirely independently of the C language specification. Despite the languages being distinct in terms of specification, every production C++ compiler also claims to be a conforming C compiler. Further, C++ standard library implementations eventually need to use C interfaces to communicate with the host operating system. So I think it is in the best interests of WG21, users of C++, and C++ implementers for WG14 to minimize incompatibilities with C++. Based on my experience as the former C and C++ compatibility study group chair and from being on both of these committees for about a decade, I think WG14 spends a significantly larger percentage of committee time on C and C++ compatibility than WG21 does. WG14 has a charter that mandates we minimize these incompatibilities (WG21 has no such mandate as they do not have a charter). The WG14 committee spends a considerable amount of meeting time deliberating how changes to C will impact C++ and our convener regularly reminds us of our obligations to minimize incompatibilities where possible. Comparatively, WG21 spends relatively little committee time on C compatibility and WG21 leadership does not proactively attempt to steer the committee to minimize incompatibilities. Given the difference in size between our committees (WG21 is approximate 15x larger than WG14), this is not a tenable situation. The committee with the least resources is spending the most time on compatibility despite reaping the least benefits. I believe compatibility with C++ should not be a chartered requirement for features brought into C that are present in C++. Without closer cooperation between WG21 and WG14 (such as a shared base document between the two languages), I do not think WG14, C implementers, or C users get sufficient benefit for the amount of WG14 committee effort spent on compatibility with C++. Unfortunately, an inability for the committees to effectively collaborate hurts the people least represented on either committee: users working in this shared space. Therefore, I do believe compatibility with C++ should continue to be a goal as a design principle, especially for features that are likely to be used in header files shared between a mixed C and C++ code base. Maintain conceptual simplicity. I still believe in this principle, though it’s a bit too ambiguous for my tastes. What one committee members finds to be simple, another might find to be too complex. For example, is a feature for overloading operators maintaining conceptual simplicity? I suspect asking five committee members that exact question will net about seven different answers. Trust the programmer, as a goal, is outdated in respect to the security and safety programming communities. I don’t think this goes far enough. I think “trust the programmer” has lead to decades of security vulnerabilities, to the point that major government agencies are now recommending against using C (and C++). I would prefer we take a stronger stance along the lines of: do not trust the programmer. Design facilities such that their misuse becomes almost impossible outside of pathological code. Prefer “defined” behavior (well-defined, implementation-defined, or unspecified behaviors) to undefined behavior where possible. When misuse is possible, require strong error detection mechanisms which can prevent undefined behavior. I think it’s perfectly reasonable to expect “trust me, I know what I’m doing” users to have to step outside of the language to accomplish their goals and use facilities like inline assembly or implementation extensions. Application Programming Interfaces (APIs) should be self-documenting when possible. I agree with the idea, but I don’t agree with the way it is presented regarding preference for VLA interfaces. That’s reasonable guidance for new APIs unrelated to any existing APIs, but it is not defensible when adding new APIs that are related to existing ones. e.g., adding memset_explicit should not (and thankfully did not) rearrange parameter order to fit this guidance, because it would have been very hard for people to migrate existing uses of memset to memset_explicit without introducing memory-related errors. I would prefer we made the guidance more general and less about VLAs. What’s Missing? To me, the biggest thing we’re missing is a plan. ISO standards committees are “obligated” to consider all proposals from committee members, and so the approach the committee takes is to take whatever papers arrive and try to give the author feedback so that they can make progress. That said, our obligations do not include a mandate on when to schedule discussion of papers — we could elect to consider papers that aren’t in the committee’s plan only after considering all other in-scope work. But the committee has never gone to those lengths and so we release standards with a hodge podge of unrelated features and bug fixes. I would love to see the committee charter require that we come up with a roadmap of what we want to accomplish in a given release cycle and then stick to that road map. I don’t mind considering occasional out-of-scope work during the cycle, but that should not come at the expense of in-scope work. I think having a roadmap will also help the relationship between the committee, implementers, and users because it gives everyone more time to plan for what’s coming in the next few years. The #1 thing I want to see on that roadmap is a goal to address the memory safety issues that plague C. We don’t have to fix everything at once, but we do need to start making inroads into solving the problem. Closing Thoughts Regardless of whether others on the committee agree with my current thinking, I think it’s a great thing that committee is reflecting on our charter. I think C is at an inflection point in many ways the should spend time carefully considering what we want the future of the language to look like. I don’t think C or C++ will be irrelevant any time soon, but I do worry they’re heading that direction and will continue to do so without course correction. No programming language is “too big to fail”, not even something as venerable and ubiquitous as C.
The year is 2023 and you’re asking “What’s new in C?” Surely the answer is “absolutely nothing”, right? Wrong! C23 will be released in the coming months (likely in early 2024), and this is a whirlwind tour of what changes … Continue reading →
The year is 2023 and you’re asking “What’s new in C?” Surely the answer is “absolutely nothing”, right? Wrong! C23 will be released in the coming months (likely in early 2024), and this is a whirlwind tour of what changes were made for the latest revision of one of the world’s most popular programming languages. I originally prepared this talk for NDC Tech Town in Kongsberg, but I was unable to give the talk because a hurricane + poor airline services interrupted my travel plans. Oh well, their loss is your gain! I hope you enjoy the talk. Errata The slide about underlying enumeration types did not make it clear that the choice of the underlying type for the enumeration type is implementation-defined, so the given types in the comments might be incorrect depending on your implementation. When mentioning that signed overflow is still implementation-defined, I misspoke. I was talking about this situation involving unsigned -> signed conversion: unsigned int i = UINT_MAX; signed int j = i; // Implementation-defined behavior However, signed *overflow* is still undefined behavior, as it always was. e.g., signed int i = INT_MAX + 1; // Undefined behavior
Don’t use the likely or unlikely attributes
C++20 introduced the likelihood attributes likely and unlikely as a way for a programmer to give an optimization hint to their implementation that a given code path is more or less likely to be taken. On its face, this seems … Continue reading →
C++20 introduced the likelihood attributes likely and unlikely as a way for a programmer to give an optimization hint to their implementation that a given code path is more or less likely to be taken. On its face, this seems like a great set of attributes because you can give hints to the optimizer in a way that is hopefully understood by all implementations and will result in faster performance. What’s not to love? The attribute is specified to appertain to arbitrary statements or labels with the recommended practice “to optimize for the case where paths of execution including it are arbitrarily more likely|unlikely than any alternative path of execution that does not include such an attribute on a statement or label.” Pop quiz, what does this code do? if (something) { likely; unlikely; foo(something); } Sorry, but the answer key for this quiz is currently unavailable. However, one rule you should follow about how to use these attributes is: never allow both attributes to appear in the same path of execution. Lest you think, “but who would write such bad code?”, consider this reasonable-looking-but-probably-very-unfortunate code: #define MY_COOL_ASSERT(x) unlikely assert(x) if (something) { likely; MY_COOL_ASSERT(something > 0); foo(something); } Despite the name, these attributes do not mark whether the statement itself is likely, only whether the path leading to the statement is likely. This brings us to our second rule: only mark the dominating statement or label of the flow control path you want to optimize for. This will often mean you only mark the compound statement after a flow control statement, as in: if (foo) likely { do_something(foo); } while (bar) unlikely { ; } switch (baz) { likely case 0: whatever(); break; unlikely case 1: something_else(); break; default: break; } Speaking of code that looks reasonable when you apply the attribute to the dominating statement of flow control, what does this code do? if (foo) likely { // A baz(); } else if (bar) likely { // B quux(); } else unlikely { // C bing(); } It marks the true branch at A as being likely and says nothing about the false (else) branch (making it unlikely by default). It then marks the true (if) branch at B as being likely and has a redundant (but harmless) unlikely attribute at C. What it does not do is mark that A and B are equally likely and C is unlikely; it will optimize the path for A over B rather than treat them as equals. The issue is that the attribute is not written on the dominating statement of flow control, and the code should be written as: if (foo) likely { // A baz(); } else likely if (bar) likely { // B quux(); } else unlikely { // C bing(); } However, because of the duplicate likely branches at A and B (on the else), it’s not clear what the implementation will do with the construct from reading the code (not to mention that it’s super ugly and unintuitive code). Because of this, the initial rule should be augmented to be: Never allow multiple likelihood attributes to appear in the same path of execution. This sort of confusion comes up in other places as well. Pop quiz, which cases are likely and which cases are unlikely in the following? switch (foo) { case 0: likely case 1: unlikely case 2: bar(); break; likely case 3: default: baz(); break; Sorry, I still can’t find the answer key. Given that case 1 looks to be likely, but it falls through to case 2 which looks to be unlikely, it’s hard to say what should happen here. Further, it’s hard to say whether the default case is likely given that case 3 is likely. The only unambiguous cases are that case 0 say nothing about whether it is or isn’t likely and case 3 is likely. Unfortunately, the wording from the standard leaves a bit to be desired when considering switch statements because it says “A path of execution includes a label if and only if it contains a jump to that label.” A switch statement contains a path of execution which can jump to any of its labels, so when you couple this recommended practice with the earlier one about applying to arbitrary statements, you have to work to answer whether this code path is likely, unlikely, or something else: if (foo) { // is this branch likely or unlikely? switch (*foo) { likely case 0: bar(); break; unlikely case 1: baz(); break; likely default: quux(); break; } } else { ... } Now, a sensible person would look at this and say “aha, those attributes shouldn’t impact the if statement because they’re within a different control flow statement with its own substatements.” Well, unfortunately the standard doesn’t say anything about how recursive these attributes should be treated. For instance, one would certainly hope that an implementation allowing attributes on arbitrary statements would do something reasonable with this: if (foo) { // Is this path likely? { likely; SomeRAIIObject Obj; Obj.whatever(foo); } } else { ... } The standard also doesn’t say what happens when you follow my rule to only mark the dominating statement or label and that leads to a conflict like this (with thanks to Arthur O’Dwyer for the example): if (ch == ' ') likely { goto whitespace; // A } else if (ch == '\n' || ch == '\t') unlikely { goto whitespace; // B } else { foo(); } likely whitespace: bar(); // C The likely attribute at C says the path at both A and B are likely, despite the path of B being marked as unlikely. Which attributes, if any, are ignored? Who knows — in all of these circumstances, the standard says nothing and so implementations will likely come up with different answers to different situations. This brings me to the next rule: assume no two implementations will behave the same way for optimizing using these attributes. So given all of these odd issues with the attributes, why would you want to use them? In my mind, there are only two use cases for the likelihood attributes. Either you have an implementation which does not support profile-guided optimizations (which will generally do a far better job of predicting branch weights for optimization than a programmer ever could) or you need to optimize a code path in a strange way where you cannot use PGO. The first question is the easier one to address: can you point to a C++20 implementation that doesn’t support profile-guided optimizations? I can’t find one. Maybe these implementations really do exist, but the major vendors all support the concept, so this isn’t a very compelling argument for adding the attributes to your own code unless you’re in that situation. That is why my rule is: prefer profile-guided optimization over likelihood attributes. It is more suited to the purpose of optimizing flow control and is likely to result in better performing code. The second situation is more interesting to talk about because it seems off-the-wall until you understand it. Sometimes you want to optimize the failure path that almost never gets hit rather than the common paths that do. Consider writing some safety-critical piece of code to control an elevator where you need the failure path to meet some real-time obligations in order to stop the elevator from dashing its occupants to death. In that situation, your optimization needs can’t be met by PGO and the likelihood attributes could be very useful. Consider this use case which came up during the standards discussions about the feature: try { foo(); } catch (...) likely { dont_kill_people(); } This is an attempt to convince the optimizer to optimize the catch statement control flow path, but it has three problems that may not be obvious from looking at the code. The first problem is a small one, the attribute is misnamed for its use in this case, which makes the code far harder to read than it needs to be. The second problem is that the C++ grammar doesn’t allow you to write the attribute at that position! You’d have to put the likely attribute inside of the catch block’s compound statement. The final problem is: implementations typically have no idea how to optimize the failure path for C++ exceptions. So these attributes failed to address the intended need in this circumstance, which is another rule: not all flow control paths can be optimized. Exception handling, setjmp/longjmp, the branches in a ?: operator are all examples of flow control where the likelihood attributes either cannot be written or may look like they’ll do something useful, but likely won’t (pun totally intended). Let’s review the rules we’ve got so far: 0) Never allow multiple likelihood attributes to appear in the same path of execution. 1) Only mark the dominating statement or label of the flow control path you want to optimize for. 2) Assume no two implementations will behave the same way for optimization behaviors with these attributes. 3) Prefer profile-guided optimization over likelihood attributes. 4) Not all flow control paths can be optimized. These attributes are starting to look a bit more like some other code constructs we’ve seen in the past: the register keyword as an optimization hint to put things in registers and the inline keyword as an optimization hint to inline function bodies into the call site. Using register or inline for these purposes is often strongly discouraged because experience has shown that optimizer implementations eventually improved to the point where they were consistently better at optimizing than the user trying to give their own hints. However, at least the register and inline keywords have other semantic impact (like not being able to take the address of a register variable in C). The likelihood attributes have no semantic impact beyond their optimization hints. Given how hard it is to use these attributes properly (especially if the code is being compiled by multiple implementations), how good profile-guided optimization is by comparison, and that there is no semantic impact from the attribute, my recommendation is to never use the likelihood attributes. They’re just not worth it.
One of the lesser-known features of C++11 is the fact that you can overload your non-static member functions based on whether the implicit this object parameter is an lvalue reference or an rvalue reference by specifying a functions ref-qualifier. This … Continue reading →
One of the lesser-known features of C++11 is the fact that you can overload your non-static member functions based on whether the implicit this object parameter is an lvalue reference or an rvalue reference by specifying a functions ref-qualifier. This feature works similar to the way cv-qualifiers work when specifying a method must be called on a const or volatile object, and can in fact be combined with cv-qualifiers. To specify a ref-qualifier for a member function, you can either qualify the function with & or &&. (The ref-qualifier must come after any cv-qualifiers.) For instance, if you wanted to declare a function to be called on an rvalue reference object only, you would write: struct S { void func() &&; }; S s1; s1.func(); // Ill-formed S().func(); // OK If you want to overload a function based on the rvalue-ness of the implicit object parameter, you must specify the ref-qualifier for both functions. struct S { void func() &; void func() &&; }; S s1; s1.func(); // OK, calls S::func() & S().func(); // OK, calls S::func() && Overloading based on a ref-qualifier is useful in (somewhat rare) circumstances where your object can make use of move semantics to reduce expensive construction costs. For instance: #include <iostream> #include <utility> class ExpensiveState {}; // Details unimportant class Builder { ExpensiveState State; public: Builder() = default; Builder(const Builder &O) : State(O.State) { std::cout << "Copy" << std::endl; } Builder(Builder &&O) : State(std::move(O.State)) { std::cout << "Move" << std::endl; } Builder operator()() & { return Builder(*this); } Builder operator()() && { return Builder(std::move(*this)); } }; int main() { Builder b; b()()()(); } When executed, this code will output: Copy Move Move Move. The Copy is because b is an lvalue, not an rvalue, and so operator()() & will be called. However, the results of that function are an rvalue, and so the subsequent subexpressions will result in calling operator()() &&. Due to this, resources can be stolen from one invocation to the next on the last three subexpressions, reducing the performance penalties of a copy operation. In case you are wondering why the std::move(*this) is used when constructing a Builder object; the unary expression *this always results in an lvalue, which would end up calling the copy constructor instead of the move constructor. So the std::move call is required to convert the lvalue into an rvalue. Ref-qualifiers are not something you will likely use often. However, it is never a bad thing to understand the tools the programming language has to offer. Note: ref-qualifiers are currently supported by clang (tested with 3.4), gcc (tested with 4.9) but not MSVC 2013.
In C++, there are two forms of binary operator overloading you can use when designing an API. The first form is to overload the operator as a member function of the class, and the second form is to overload the … Continue reading →
In C++, there are two forms of binary operator overloading you can use when designing an API. The first form is to overload the operator as a member function of the class, and the second form is to overload the operator as a friend function of the class. I want to explore why you would use one form of overloading instead of the other, using a Fraction class as an example. For the purposes of this discussion, this is part of the interface for our expository class. class Fraction { // Implementation details live here. public: Fraction(int Whole); Fraction(int Numerator, unsigned Demoninator); Fraction(double Value); // Binary operator overloads live here. }; One of the ways we can implement our binary operator overloads is as member functions of the Fraction class. I’m going to pick on the equality operator, but any of the overloaded binary operators would suffice. ... // Binary operator overloads live here. bool operator==(const Fraction &RHS) const; ... The other way we can implement our binary operator overloads is as a friend function of the Fraction class. ... // Binary operator overloads live here. friend bool operator==(const Fraction &LHS, const Fraction &RHS); Since there are two different ways to implement this, it’s reasonable to ask which way is “correct?” The answer to that question depends on your intentions as a class designer. Consider the following use case: void f(const Fraction &F) { if (1.0 == F) { // Do something interesting } } Some coding conventions suggest that equality comparisons against a constant value put the constant on the left-hand side of the comparison (so that an accidental assignment operation by typing = instead of == would trigger a compile error), so this example is not particularly far-fetched. If you use a member function for the operator overload, this code would not compile because there’s no way for the implicit converting constructor from double to Fraction to be called. However, by using a friend function for the operator overload, the compiler can call the converting constructor to create a Fraction object which would make the comparison viable. Because of this, I would claim that declaring the operators to be friends is the correct approach for the class design. This exemplifies a reasonable way to decide how to implement the overloaded binary operators. If you want to allow implicit conversions for items on the left-hand side of the operator, then using friend function overloads is required. If implicit conversions are not desirable for some reason, or not possible (due to having no implicit converting constructors), then using a member function is acceptable. If you’re looking for a general rule of thumb, I would recommend always using the friend function form — it’s more likely to behave how the user would expect in all cases, instead of having curious edge cases where their usage fails. Imagine how confusing it would be for the user of a Fraction class that SomeFraction * 1 succeeds, but 1 * SomeFraction fails to compile! That being said, it ultimately boils down to a design choice that you must make as a class designer. I would like to thank Jens Maurer for the design discussion which spawned this blog posting.
Implementing a four-bit adder with C++ template metaprogramming
I recently read a post by Phillip Larkson where the C preprocessor was used to implement a four-bit adder entirely at compile time. This got me wondering whether I could implement the same concept using C++ template metaprogramming. It seemed … Continue reading →
I recently read a post by Phillip Larkson where the C preprocessor was used to implement a four-bit adder entirely at compile time. This got me wondering whether I could implement the same concept using C++ template metaprogramming. It seemed theoretically possible as all the components can be calculated at runtime, but I wanted to avoid making use of the preprocessor for anything but supplying the original values to be added. The goal was to compile something on the command line like: clang -DNUMBER_1=5 -DNUMBER_2=7 foo.cpp and have the value 12 written out to the command line. It turns out that this is relatively straight-forward to implement in C++. You can encode the bitwise operators AND and XOR with template specializations, and the remainder of the adder is bookkeeping for the sum and carry bits. The bitwise operators and adder themselves look like: struct one_bit { static const unsigned value = 1; }; struct zero_bit { static const unsigned value = 0; }; template <unsigned A1, unsigned B1> struct and_op : public zero_bit {}; template <> struct and_op<1, 1> : public one_bit{}; template <unsigned A1, unsigned B1> struct xor_op : public zero_bit {}; template <> struct xor_op<1, 0> : public one_bit{}; template <> struct xor_op<0, 1> : public one_bit{}; template <unsigned A1, unsigned B1, unsigned cin> struct full_adder { static const unsigned sum = xor_op<xor_op<A1, B1>::value, cin>::value; static const unsigned carry = xor_op<and_op<xor_op<A1, B1>::value, cin>::value, and_op<A1, B1>::value>::value; }; I define a pair of base structures to represent a zero bit and a one bit. The base operator is not specialized, and results in the zero bit. The specializations for the operators return the one bit for the correct operands. The full_addr structure implements the typical sum and carry operations which are described on Wikipedia. As I mentioned, implementing the four-bit adder is a matter of bookkeeping for the bits, and so I made a helper structures called two_bit_addr and four_bit_addr_inner to do the bookkeeping. The implementation of each is to hook up the full_addr in a serialized fashion. I suspect there’s a way to make a generalized N-bit adder using template parameter packing, but I didn’t give the design enough though to prove it’s possible. template <unsigned A0, unsigned A1, unsigned B0, unsigned B1, unsigned C0> struct two_bit_adder { private: static const unsigned c1 = full_adder<A0, B0, C0>::carry; public: static const unsigned s0 = full_adder<A0, B0, C0>::sum; static const unsigned s1 = full_adder<A1, B1, c1>::sum; static const unsigned carry = full_adder<A1, B1, c1>::carry; }; template <unsigned A3, unsigned A2, unsigned A1, unsigned A0, unsigned B3, unsigned B2, unsigned B1, unsigned B0, unsigned C0> struct four_bit_adder_inner { private: static const unsigned c1 = two_bit_adder<A0, A1, B0, B1, C0>::carry; public: static const unsigned s0 = two_bit_adder<A0, A1, B0, B1, C0>::s0; static const unsigned s1 = two_bit_adder<A0, A1, B0, B1, C0>::s1; static const unsigned s2 = two_bit_adder<A2, A3, B2, B3, c1>::s0; static const unsigned s3 = two_bit_adder<A2, A3, B2, B3, c1>::s1; static const unsigned carry = two_bit_adder<A2, A3, B2, B3, c1>::carry; }; In order to fit the design I wanted, I needed some helpers that would convert a decimal value into a series of binary digits, and binary digits into a decimal value. This way, I could specify decimal values on the command line, convert them into binary values to pass to the adder, and then convert the binary result from the adder back into a decimal value. The binary conversion uses recursive template definitions to determine each bit of the value. Given a decimal input and a bit index, it returns the bit value at that index. template <unsigned N, unsigned BN> struct to_bin_helper { static const unsigned value = to_bin_helper<(N >> 1), BN - 1>::value; }; template <unsigned N> struct to_bin_helper<N, 0> : to_bin_helper<N & 1, 0>{}; template <> struct to_bin_helper<1, 0> : one_bit{}; template <> struct to_bin_helper<0, 0> : zero_bit{}; template <unsigned Num, unsigned Bit> struct to_bin { static const unsigned value = to_bin_helper<Num, Bit>::value; }; To convert from binary back to decimal, I used template parameter packing from C++ to represent the bits in the binary number, and the resulting value is a straight binary-to-decimal calculation using recursive template definitions to perform the calculation. This, of course, requires the ability to get power-of-two values for which I used another recursive template definition. template <unsigned N> struct pow2 { static const unsigned value = 2 * pow2<N - 1>::value; }; template <> struct pow2<0> { static const unsigned value = 1; }; template <unsigned N, unsigned S, unsigned... Rest> struct to_dec_helper { static const unsigned value = (S * pow2<N>::value) + to_dec_helper<N + 1, Rest...>::value; }; template <unsigned N, unsigned S> struct to_dec_helper<N, S> { static const unsigned value = S * pow2<N>::value; }; template <unsigned Bit1, unsigned... BitN> struct to_dec { static const unsigned value = to_dec_helper<0, Bit1, BitN...>::value; }; Finally, I could put all of these helpers together to create the four-bit adder structure. It accepts two decimal values which are converted into binary values when passed to the inner four-bit adder helper. The inner helper performs the calculation and returns the bits for the result. These bits are then passed into the binary-to-decimal helper which returns the resulting decimal value. All of this happens within the template system and results in a constant value. template <unsigned A, unsigned B> struct four_bit_adder { static const unsigned value = to_dec<four_bit_adder_inner<to_bin<A, 3>::value, to_bin<A, 2>::value, to_bin<A, 1>::value, to_bin<A, 0>::value, to_bin<B, 3>::value, to_bin<B, 2>::value, to_bin<B, 1>::value, to_bin<B, 0>::value, 0>::s0, four_bit_adder_inner<to_bin<A, 3>::value, to_bin<A, 2>::value, to_bin<A, 1>::value, to_bin<A, 0>::value, to_bin<B, 3>::value, to_bin<B, 2>::value, to_bin<B, 1>::value, to_bin<B, 0>::value, 0>::s1, four_bit_adder_inner<to_bin<A, 3>::value, to_bin<A, 2>::value, to_bin<A, 1>::value, to_bin<A, 0>::value, to_bin<B, 3>::value, to_bin<B, 2>::value, to_bin<B, 1>::value, to_bin<B, 0>::value, 0>::s2, four_bit_adder_inner<to_bin<A, 3>::value, to_bin<A, 2>::value, to_bin<A, 1>::value, to_bin<A, 0>::value, to_bin<B, 3>::value, to_bin<B, 2>::value, to_bin<B, 1>::value, to_bin<B, 0>::value, 0>::s3 >::value; }; The resulting program is trivial — it expects the values to be added to come from the command line via the preprocessor: int main(void) { static const unsigned ret = four_bit_adder<NUMBER_1, NUMBER_2>::value; ::printf("%d\n", ret); return 0; } Executing it from the command line results in the expected values: E:\llvm\2013>clang -std=c++11 -DNUMBER_1=7 -DNUMBER_2=4 "E:\Aaron Ballman\Deskto p\test.cpp" E:\llvm\2013>a.out 11 E:\llvm\2013>clang -std=c++11 -DNUMBER_1=9 -DNUMBER_2=4 "E:\Aaron Ballman\Deskto p\test.cpp" E:\llvm\2013>a.out 13 Thanks to Phillip for giving me the idea to do this! The full source code can be downloaded from here, and it’s been tested and works with clang 3.4 (ToT), gcc 4.8.1 and Visual Studio 2013.
Interesting Note About the sizeof Operator
The expression used in a sizeof operator is an unevaluated expression in C and C++. This can make for some surprising situations if you are unaware of it. For instance: #include <stdio.h> int main( void ) { int a = … Continue reading →
The expression used in a sizeof operator is an unevaluated expression in C and C++. This can make for some surprising situations if you are unaware of it. For instance: #include <stdio.h> int main( void ) { int a = 12; int b = sizeof( ++a ); printf( "%d\n", a ); return 0; } This code will print 12 instead of 13 because the expression ++a is unevaluated. So what does it mean for an expression to be unevaluated? Basically, it means that the expression is used at compile time only as a way to determine a type, which is then used to evaluate the result of the sizeof operator. So in the above example, a’s type is determined, and the resulting type for ++ is determined, but no code is generated to execute the ++. Here’s an abusive example that demonstrates this: #include <stdio.h> class c { public: double operator++(); }; int main(int argc, char *argv[]){ c c1; int i = sizeof( ++c1 ); int j = sizeof( c1 ); ::printf( "%d, %d\n", i, j ); return 0; } If you run this code, you will see 8, 1 printed and will not get a link error (because of the failure to define operator++)!
One of the lesser-known features of Visual Studio’s C/C++ compiler are the pointer type attributes __ptr32 and __ptr64. More information about them can be found on MSDN. These pointer type attributes are used to control the visible size and behavior … Continue reading →
One of the lesser-known features of Visual Studio’s C/C++ compiler are the pointer type attributes __ptr32 and __ptr64. More information about them can be found on MSDN. These pointer type attributes are used to control the visible size and behavior of pointers in 32- and 64-bit applications. Their usage is a bit strange, but if you need to do interop between 32- and 64-bit mode, they can be handy features to have. Additionally, there are the __sptr and __uptr qualifiers which allow you to specify how the pointer types are extended. __sptr denotes sign extension, and __uptr denotes zero extension. Information about these qualifiers can also be found on MSDN. The behavior of these type attributes is strange, to say the least. I wanted to take a moment to document what I’ve observed the behavior to be, as of Visual Studio 2012. For starters, the documentation is a bit misleading for __ptr32 and __ptr64. Specifically, the documentation states: On a 32-bit system, a pointer declared with __ptr64 is truncated to a 32-bit pointer. On a 64-bit system, a pointer declared with __ptr32 is coerced to a 64-bit pointer. However, this isn’t strictly accurate. When you use a type with a specific pointer size, the returned pointer will be sized accordingly regardless of architecture you are targeting. For instance, if you use __ptr64 on an x86 build, you will get a 64-bit pointer value. If you pass it to functions, use it in structures, call sizeof on it, etc, it will occupy 8 bytes of space, even though you are on a 32-bit system. However, when you dereference the pointer, it will only use the low 32-bits of the pointer. For instance: #include <stdlib.h> void func( int * __ptr64 p ) { *p = 12; } int main( void ) { int * __ptr64 p = (int * __ptr64)::malloc( sizeof( int * __ptr64 ) ); func( p ); return 0; } If you compile this code and take a look at the resulting disassembly, you will notice some interesting behaviors: mov esi, esp ; sizeof( int * __ptr64 ) yields 8 push 8 ; call malloc call DWORD PTR __imp__malloc add esp, 4 cmp esi, esp call __RTC_CheckEsp ; convert the 32-bit pointer to a 64-bit value cdq ; store both parts of the 64-bit value into a 64-bit variable mov DWORD PTR _p$[ebp], eax mov DWORD PTR _p$[ebp+4], edx ; push both halves of the pointer onto the stack mov eax, DWORD PTR _p$[ebp+4] push eax mov ecx, DWORD PTR _p$[ebp] push ecx ; call func and then cleanup the 8 bytes on the stack when done call ?func@@YAXPEAH@Z add esp, 8 ; this is the implementation of func itself ; notice that it only uses the low 32-bits of the pointer ; when dereferencing and assigning in the value 12 mov eax, DWORD PTR _p$[ebp] mov DWORD PTR [eax], 12 So while you are asking for a 64-bit pointer, and actually receive a 64-bit value in response, you really can only use 32-bits of it which is what the MSDN documentation is alluding to. Considering that __ptr32 and __ptr64 yield types of different sizes, you might expect the types to differ such that you can overload on them. For instance, you can overload based on long and long long types. Additionally, if you view them as qualifiers (like const or volatile), you can also overload. So what about __ptr32 and __ptr64? It turns out that the compiler treats these qualifiers as sugar instead of as part of the canonical type, so you cannot overload based on them. void f( int * __ptr64 i ) {} void f( int * __ptr32 i ) {} void f( int * i ) {} This will yield two errors stating: function 'void f(int * __ptr64)' already has a body Okay, so the types aren’t different canonically as far as function overloading is concerned. Yet they are considered different types as far as conversions go: int * __ptr64 p1 = 0; int * __ptr32 p2 = p1; Compiling this code yields the warning: warning C4244: 'initializing' : conversion from 'int * __ptr64' to 'int * __ptr32__ptr32 ', possible loss of data As if this isn’t confusing enough, the name mangler implies the types are different! void f( int * __ptr64 i ) {} void f2( int * __ptr32 i ) {} PUBLIC ?f@@YAXPEAH@Z ; f PUBLIC ?f2@@YAXPAH@Z ; f2 So as far as the name mangler is concerned, they are different types! __sptr and __uptr fit into the equation as pointer type qualifiers that affect how pointers are extended. If you specify __sptr, the pointer will be sign extended. If you specify __uptr, it will be zero extended. Modifying our x86 example slightly: void func( int * __ptr64 p ) { *p = 12; } int main( void ) { int * __ptr32 __uptr p = (int * __ptr32 __uptr)::malloc( sizeof( int * __ptr32 __uptr ) ); func( p ); return 0; } We’ve added the __uptr qualifier to the variable p in main. This means that when p is converted to a 64-bit pointer as an argument to func, it will be zero extended instead of sign extended. Looking at the disassembly shows this to be true: ; Allocate a 32-bit pointer by calling malloc push 4 call DWORD PTR __imp__malloc add esp, 4 ; Store the 32-bit value into p mov DWORD PTR _p$[ebp], eax ; Convert p into a 64-bit pointer by zero extending it ; when passing it to func mov eax, DWORD PTR _p$[ebp] xor ecx, ecx push ecx push eax ; Call func, and then clean up the 8 bytes on the stack call ?func@@YAXPEAH@Z ; func add esp, 8 The semantics for __sptr and __uptr are a bit more consistent than __ptr32 and __ptr64 as they don’t affect warning semantics, overload semantics, or the name mangler. However, that leaves them with their own peculiar quirks. int * __sptr p1 = 0; int * __uptr p2 = p1; This code will compile without warning, because as far as the compiler is concerned, __sptr and __uptr only affect code generation, and not semantics. Additionally, template specialization treats them as equivalent, so when a template is instantiated, it gets whatever pointer qualifiers are on the first instantiation. For instance) template<typename T> void f(void **p, T *q) { *p = *q; } void *g(int *__ptr32 __sptr a) { void *result; f(&result, &a); return result; } void *h(int *__ptr32 __uptr a) { void *result; f(&result, &a); return result; } void *i(char * __ptr32 __uptr a ) { void *result; f(&result, &a); return result; } int main() { printf("%p\n", g((int *__ptr32 __sptr)0xdeadbeef)); printf("%p\n", h((int *__ptr32 __uptr)0xdeadbeef)); printf("%p\n", i((char *__ptr32 __uptr)0xdeadbeef)); } If you run this code, you will see the first two pointers being sign extended, and the last one being zero extended. This happens because the template instantiation is pulling in the __sptr from the first call, not generating a new instantiation for the second call, but doing so for the third call. Consequently, you can’t really trust the MSDN documentation on __sptr and __uptr when it comes to what’s allowed and what isn’t allowed. I’ve already filed these Connect reports on the topic: Apply __sptr and __uptr to pointer to members Specify __sptr and __uptr on the same type Allowed to specify __sptr or __uptr on a non-pointer type All this being said, __ptr32, __ptr64, __sptr and __uptr aren’t things you are likely to ever use unless you happen to be doing some highly specific work. But hopefully this sheds a bit of light on the weird behavior of these quirky features!
Just because I’ve not written many posts lately doesn’t mean I’ve been silent. You should go check out the Tidbits page, it currently has over 20 little juicy pieces of information about C and C++. I’ve been using it as … Continue reading →
Just because I’ve not written many posts lately doesn’t mean I’ve been silent. You should go check out the Tidbits page, it currently has over 20 little juicy pieces of information about C and C++. I’ve been using it as a training exercise for my coworkers, and it’s been very successful so far. I’ll likely be continuing with regular Friday updates of Tidbits for quite a while to come. I do hope to write some more full-length blog posts now that life is starting to settle back down again. So I’m not dormant, honest!
Variable argument lists are very arcane in the world of C. You’ll see them expressed in function signatures as … at the end of the parameter list, but you may not understand how they work or what they do. There … Continue reading →
Variable argument lists are very arcane in the world of C. You’ll see them expressed in function signatures as … at the end of the parameter list, but you may not understand how they work or what they do. There are two sides to every function at runtime: the caller and the callee, and they both need to agree on the semantics of how the function call works (how do parameters get passed, return values returned, etc). The caller’s side is pretty easy with variable arguments because the compiler will continue to pass parameters like it normally would, right up until the terminating parenthesis. For the caller, it’s no different than any other function call except for the fact that the compiler will allow any number of arguments (including zero) after the initial parameters. They all get pushed onto the stack (depending on architecture and calling conventions) in the proper order, and the callee is responsible for figuring them out. The callee side, on the other hand, is quite interesting. Let’s take a look at a typical function: void foo( int bar, ... ) { va_list args; va_start( args, bar ); for (;;) { some_type t = va_arg( args, some_type ); /* Do something with t */ } va_end( args ); } The way it works on the callee side is that you must use the “va” functions: va_start, va_arg and va_end as a way to query for the parameter list. The first thing you’ll notice is the only way to call va_start is by passing in the last parameter in the list (the parameter preceding the …). This is because the only way for variable argument lists to work is for the callee to know where the function parameters live, and you can only do that if you have at least one formal parameter. Because va_start needs the exact location of the parameter, it is a macro instead of a function — this allows it to get at the address of the parameter on the correct stack. Once you’ve gotten the start of the va_list, you get each individual argument by using the va_arg macro. This macro takes the list as well as a type, translates into the actual argument value, and advances the list to the next parameter. va_end is called when completed to clean up. There’s no compiler magic required for this implementation, everything can be done with vanilla C functionality. This has some interesting ramifications. For instance, you must know where to stop looking for arguments or else you will walk off the end of the argument list. Also, this means that the function taking a variable argument list must be declared as __cdecl because the caller is the only one who knows how to properly clean up the call stack (the callee doesn’t know how many parameter were passed to it, remember?). Finally, in order to walk the list, you must know exactly what types are expected in what order. If you don’t, then when va_arg attempts to read in a parameter, it may give you garbage by reading too much or too little memory. And when it advances to the next argument, it may do the same because the previous argument’s size information was wrong. To better understand what I am talking about, this is a hint as to how these macros might be implemented on x86: typedef unsigned char *va_list; #define va_start(list, param) (list = (((va_list)&param) + sizeof(param))) #define va_arg(list, type) (*(type *)((list += sizeof(type)) - sizeof(type))) They may look dense, but they’re rather simplistic in their implementation. The va_list is nothing more than a byte pointer. va_start assigns the address of the first parameter *after* the one passed in. va_arg advances the byte pointer by the parameter size and stores it, then backs up a bit to grab the actual value. So variable argument lists aren’t as powerful or easy to use as they are in other languages like C# or Python. They basically are at the mercy of the programmer. But now you probably understand why you have to put all the type information into a printf format specification, or why you need to specify sentinel values to terminate lists.