Single-byte key addressing (for boards with fewer than 256 keys)


(Michael Richters) #21

I’ve made a “keyaddr” branch in my Arduino-Boards fork that contains all the changes I’ve made so far. Here’s the diff, which unfortunately contains a few extra things because I started from the master branches of the submodules, not the current head of keyboardio/Arduino-Boards. I think my changes are still clear, though.


(Noseglasses) #22

I have now checked your changes. It looks promising. I definitely would wrap everything related to keyaddr in a POD class that features nice constexpr access functions. Also it is definitely going to break existing code.

Apart from saving RAM and PROGMEM, such a change would address other aspects related to the way C++ is used in Kaleidoscope. After/while discussing with you, my brain started wandering. This led to a new topic about general improvements of Kaleidoscope.


(Michael Richters) #23

I’m sure if I had known about constexpr and how to implement it without worrying about spending hours deciphering compiler/linker errors, I would have made KeyAddr a POD class instead of a typedef.

This is not to imply that I do understand typedef, except in the use on primitives. I’m not at all sure why it exists in C++ for use with struct, union, and class types, and I invariably find it confusing in those contexts.


(Michael Richters) #24

By the way, I figured out what I had messed up with the LED addressing, and it turns out the savings aren’t quite as big as I first reported (but still ~500 bytes, and further optimizations are clearly possible) because (I think) key_led_map[] was unused, and optimized out by the compiler.

I’ll see if I can post an update this evening with more details.


(Jesse) #25

make size-map and make decompile can both be very useful for figuring things like this out.


(Michael Richters) #26

So, I started coding it as a class, similar to Key_ as suggested, and it seemed like that would be fine, but then I ran into something that I don’t know if it would work. By its nature, the KeyAddr object is used as an index to an array in quite a few places. For example:

int8_t layer = activeLayers[key_addr];

I’d also expect it to get used as an iterator:

for (KeyAddr key_addr = 0; key_addr < TOTAL_KEYS; key_addr++) { 
  Key k = liveCompositeKeymap[key_addr];
  . . .
}

Is this something that can be done with a class/struct, or is it necessary to use the more awkward notation:

Key k = liveCompositeKeymap[key_addr.addr()];

…because the latter, in my opinion, destroys the whole façade, and turns all the operator overloading convenience into a trap for programmers who don’t know the details and do some reasonable pattern-matching.


(Michael Richters) #27

I’ve tried to find out if it’s possible to define a cast operator such that using such an object as an array subscript would work properly, but I can’t find any examples or discussion of it on the internet. Overloading the subscript operator itself seems possible (perhaps even wise) but that requires even more code in any array object that wants to use a KeyAddr as an index.

It really seems like just keeping it a typedef of a primitive integer type is far, far simpler.


(Noseglasses) #28

True, but it actually would be the perfect (most safe) solution, to turn even the arrays into classes and supply them with subscript operators that operate with class KeyAddr. However, this currently seems too much.

Here is an example that demonstrates how one could implement the KeyAddr class, with the necessary operators, including a cast operator.

Please note, that cast operators are in general considered as evil as they tend to cause unintended type conversions. They are mostly used as a hack. But we could use it anyway here until we have the array classes discussed above. This would still be safer and more readable than having a typedef. Remember, typedefs are just aliases. They do not provide protection against the ‘apples and oranges’ problem.

#include <iostream>
#include <limits>
#include <assert.h>

// These would be defined through the build system to 
// provide portability, e.g. through a platform 
// dependent types-header
//
#define KALEIDOSCOPE_MATRIX_ACCESS_TYPE uint8_t
#define KALEIDOSCOPE_KEY_ADDR_STORAGE_TYPE uint8_t
#define KALEIDOSCOPE_KEYBOARD_ROW_SIZE 8

class KeyAddr 
{
   public:
      
      typedef KALEIDOSCOPE_MATRIX_ACCESS_TYPE RowType;
      typedef KALEIDOSCOPE_MATRIX_ACCESS_TYPE ColType;
      
      typedef KALEIDOSCOPE_KEY_ADDR_STORAGE_TYPE StorageType;
      
      static constexpr ColType cRowSize 
         = KALEIDOSCOPE_KEYBOARD_ROW_SIZE;
      static constexpr StorageType cInvalid 
         = std::numeric_limits<StorageType>::max();
      
      constexpr KeyAddr() : rawAddr_(0) {}
      
      constexpr KeyAddr(RowType row, ColType col) 
         : rawAddr_(row*cRowSize + col) {}
      constexpr KeyAddr(StorageType rawAddr) 
         : rawAddr_(rawAddr) {}
         
      constexpr KeyAddr(const KeyAddr &other) : rawAddr_(other.rawAddr_) {}
      constexpr KeyAddr(KeyAddr &&other) : rawAddr_(other.rawAddr_) {
         other.rawAddr_ = cInvalid;
      }
      
      KeyAddr &operator=(const KeyAddr &other) {
         rawAddr_ = other.rawAddr_;
         return *this;
      };

      KeyAddr &operator=(KeyAddr &&other) {
         rawAddr_ = other.rawAddr_;
         other.rawAddr_ = cInvalid;
         return *this;
      };
      
#define KEY_ADDR_FORWARD_OPERATOR(OP) \
      bool operator OP(const KeyAddr &other) { \
         return rawAddr_ OP other.rawAddr_; \
      }
      
      KEY_ADDR_FORWARD_OPERATOR(==)
      KEY_ADDR_FORWARD_OPERATOR(<)
      KEY_ADDR_FORWARD_OPERATOR(>)
      KEY_ADDR_FORWARD_OPERATOR(<=)
      KEY_ADDR_FORWARD_OPERATOR(>=)
      KEY_ADDR_FORWARD_OPERATOR(!=)
#undef KEY_ADDR_FORWARD_OPERATOR
      
      // Prefix
      KeyAddr& operator++()
      {
         ++rawAddr_;
         return *this;
      }
      
      // Postfix
      KeyAddr operator++(int)
      {
         KeyAddr tmp(*this); // copy
         operator++(); // pre-increment
         return tmp;   // return old value
      }    
      
      // Prefix
      KeyAddr& operator--()
      {
         --rawAddr_;
         return *this;
      }
      
      // Postfix
      KeyAddr operator--(int)
      {
         KeyAddr tmp(*this); // copy
         operator--(); // pre-increment
         return tmp;   // return old value
      }    
      
      // Note: Cast oprators are commonly considered as evil as they
      //       can cause nasty side effects when applied unintended.
      //
      operator StorageType() {
         return rawAddr_;
      }
      
      RowType getRow() const {
         return rawAddr_ / cRowSize;
      }
      
      void setRow(RowType row) {
         auto col = this->getCol();
         *this = KeyAddr(row, col);
      }
      
      RowType getCol() const {
         return rawAddr_ % cRowSize;
      }
      
      void setCol(ColType col) {
         auto row = this->getRow();
         *this = KeyAddr(row, col);
      }
      
      StorageType getRaw() const {
         return rawAddr_;
      }
      
      void setRaw(StorageType rawAddr) {
         rawAddr_ = rawAddr;
      }
   
   private:

      StorageType rawAddr_;
};

int main()
{
   int test[256];
   
   static constexpr KeyAddr maxKeys(255);
   
   KeyAddr z;
   assert(z.getRaw() == 0);
   
   KeyAddr a(1, 2); // Construction
   assert(a.getRow() == 1);
   assert(a.getCol() == 2);

   KeyAddr b(3);
   assert(b.getRaw() == 3);
   
   KeyAddr c = 1;
   assert(b.getRaw() == 1);
   
   KeyAddr d = c;
   assert(d.getRaw() == 1);
   
   KeyAddr e = std::move(d);
   assert(d.getRaw() == KeyAddr::cInvalid);
   assert(e.getRaw() == 1);
   
   KeyAddr f(std::move(c));
   assert(c.getRaw() == KeyAddr::cInvalid);
   assert(f.getRaw() == 1);
   
   for(KeyAddr k = 0; k < maxKeys; ++k /* Note: Always prefer prefix as it is usually faster (no temporary copy necessary */) {
      test[k] = k.getCol();
   }
   
   for(KeyAddr k = 0; k < maxKeys; ++k /* Note: Always prefer prefix as it is usually faster (no temporary copy necessary */) {
      std::cout << test[k] << std::endl;
   }
}
      

(Gergely Nagy) #29

Yeah, that’s a bit too much. Lets stick to uints in this case =)


(Noseglasses) #30

Are you serious? You are confronted with a solution that provides type safety, encapsulation and portability at zero runtime cost and you simply refuse it?

That makes me sad.

Kaleidoscope intents to provide a plugin API. I think it is desirable to have a first class implementation at least for the API part. Key addressing is definitely part of this.


(Gergely Nagy) #31

It is not up to me to refuse or accept it. But if it were, I’d reject it, yes. There are other costs, not just runtime: there’s the cost of complexity. The cost of making the code harder to understand for a newcomer, or someone less familiar with the language.

Type safety is in general, a good thing. In this case? We are talking about an index, pretty much. Perhaps a helper or two to turn coordinates into an index and vice-versa. Building a class around it is overkill in my opinion. It does not give us enough benefits to offset the costs. Portability can be achieved in other ways. Encapsulation? It’s an index. A number. What do we want to encapsulate on that? Type safety? It would be nice to have, but I do not feel it is such a huge win in this case. Certainly not at the cost of the complexity such a class would introduce.

I’d rather have simple, approachable code that might not be perfect, than have code that holds my hands, but makes it significantly harder to figure out what goes on behind the scenes. I’d rather have code that may not be the most C+±ish code, which does not use all the bells and whistles the language provides, but remains easily understandable, easy to work with. An unsigned integer index is simple and easy to work with. Yes, it is easier to abuse it too, but that is a price I would pay for having simpler code.

Simplicity > perfection, in my opinion.

Yeah, it is. I see nothing wrong with simple, primitive integer indexes. It perhaps is not Perfect™, it may not pass the Clean Code Test or something. But it is a perfectly fine part of an API, as it is.

While here, I’d make a counter-proposal:

namespace kaleidoscope {

typedef uint8_t key_index_t;

class KeyIndex {
  public:
    static const key_index_t fromCoordinates(byte row, byte col);
    static void toCoordinates(key_index_t index, byte &row, byte &col);
};
}

In the code, we’d use key_index_t whenever working with addresses, and kaleidoscope::KeyIndex::fromCoordinates() / kaleidoscope::KeyIndex::toCoordinates() whenever we want to convert between them. If we made a struct for row and col, we could even return that from toCoordinates, I suppose, and wouldn’t need the output params, which’d make it better. That assumes that whenever we need cordinates, we’d use the struct too, to avoid having to destructure it.

The different hardware plugins could provide the KeyIndex class too, implementing it in whatever way they prefer, along with key_index_t. Thus, we achieve portability, some amount of encapsulation too. Less type safety, but that’s something that has little benefit in this case. And the code still remains quite simple. Much simpler than your proposed KeyAddr class, while still getting us some useful benefits, even if not all of them.

It may not be the poster-child of OOP, but I’d like to entertain the idea that strict adherence to OOP principles is not always the best of ideas.


(Noseglasses) #32

Having a clean well documented class interface is the best you can do for a user. If that is available, no user will ever look it its implementation. On the contrary, in my eyes it is a very bad implementation, when a user of an interface does have to look at its implementation to understand it.

In this case, the user sees a class that has setters and getters. I obviously can serve as an index (documentation!) and that’s it. On the other hand, it cannot be abused accidentally, e.g. by assigning stupid values to it and accessing nonsense key addresses.

That’s it, exactly. And that’s the main point of encapsulation. The user is not wanted to deal with the implementation details such as the coordinate to index mapping.

There are no costs, apart from the ten minutes I spend writing it.

What complexity. We are talking about an API. The user code stays exactly the same.

What I wrote is simple, plain C++. No bells, no whistles. Are we talking about this equation?

C++ = C + whistles

That is wrong.

Here I agree. Simplicity (and safety!) for the user, not necessarily the core developer.

Having only static methods in a class and no data is pointless (unless in the context of TMP). You might rather want to use a namespace for that. Returning a const datum by value is pointless, too.


(Noseglasses) #33

To state this more precisely:

You can have an instance of class KeyIndex. What is the meaning of such an instance?


(Michael Richters) #34

I agree with @noseglasses that it would be great to improve type safety in this case. In particular, it would save us from the problem of having to rewrite calls to setCrgbAt(row, col, color) in plugins in a different way than everything else, because we can’t have two functions with the same name and parameter signature.

But I also agree with @algernon that these changes are just too complex. There’s plenty in there that I don’t understand at the moment, and that’s not all, because if we also change the arrays to classes with overloaded subscript operators, those changes aren’t limited to Kaleidoscope — any plugin that wants to store such an array also needs to duplicate that. To me, it’s way too much code for the benefit.


(Noseglasses) #35

I totally agree. That’s why I implemented the type cast operator, for not having to generate array classes :wink:


(Noseglasses) #36

One more word about APIs.

You might have used the boost C++ library before. If not, please take a look at it. Everything is very well documented. As a user I never had to look at any boost code file. I just used it. It is nice to work with as the interfaces are very well designed and everything is type safe.

But if you look at their implementations, regardless of .h or .cpp files, you will be truly scared off by the complexity of the code.

A good API is documented with tools like doxygen (or similar) and spares the user the burden to look at the interface implementation.


(Gergely Nagy) #37

I think we’ll have to agree to disagree here. As a novice, I found primitive types much easier to work with than classes. With many years of coding under my belt, I still do. No matter how well you document your class, it will rarely be as simple as primitive types. Primitive types that may be familiar from other languages.

For someone with C++ experience, a well documented class is easy. For someone without, much less so. For someone with very little programming experience, and explicit conversion may very well make more sense than hiding it behind a “magic” class. Sometimes explicit is easier to understand - when using it - than implicit. It lets the user see directly what is happening.

…but why do we even need setters/getters? It’s an index. At most, you want to convert it to and from coordinates. I still don’t see why that requires a complex class.

In that case, I’d find it more reasonable to create variants of functions that accept indexes, to also accept coordinates, and do the conversion behind the curtain. That would still be less complex.

There is. The complexity of the source code is a cost, and a non-trivial one too. Pre-processor macros, operator overloading is complexity. Complexity is a cost, and must have enough benefits to justify it.

No, we are not talking about C++ = C + whistles. What I meant that just because a language provides a great many tools which are useful and desirable in some cases, they are not useful or desirable in all cases.

Yeah, a namespace there would have been better. It was a quick example to demonstrate another option.

We could just get rid of setCrgbAt(i, color) to be honest. There are very few users of it, and all of those could easily transition to use coordinates, at worst with an explicit coordinate->index conversion. LEDEffect-Chase and LEDEffect-Rainbow use it, but could easily be made not to, as far as I see. BootAnimation uses it as well, but that whole plugin could just be dropped to be honest, or rewritten in a much better way.

Having a way to address LEDs by index, which is different from the index of the key they are under has been irritating me for quite some time. This seems like a great opportunity to fix that, too.

(Besides, LEDControl should be redone from the ground up anyway, see LEDControl#15 for reasons why.)

I used it. I had to debug it a few times. I’d rather forget that experience, thank you very much. It is a fantastic collection of libraries, very well documented, and generally good quality. But if things go wrong - and things always go wrong -, it is an absolute horror to debug code built with it. Now introduce that into a firmware setting… yikes.

I do not believe we need that kind of complexity in Kaleidoscope. That is certainly a trade off, which makes a few things perhaps less perfect. But that is a trade off I would be willing to take to keep things as simple as possible.

We agree here. But a simpler solution does not mean it can’t - or shouldn’t - be documented. We can have both, and the user still won’t have to look at the implementation.


(Adrià Casajús) #38

If it’s users you’re worried about? How about how a plugin or some user code would look like for each option? That might give you more insight/show pros and cons…

I’m more in favour of @noseglasses option since I find boost extremely useful and easy to use from the point of view of a user (but the code inside is a nightmare).


(Michael Richters) #39

Where? I see a comment about it, but I don’t understand what operator StorageType() is. I also don’t understand ~half of the code there.

This is extremely intimidating to me as someone who’s not expert at all the C++ peculiarities, and the benefits seem vanishingly small.


(Michael Richters) #40

I can’t disagree more, especially in this case. We’re writing a huge amount of code just to create a type that is an integer, but can only be used where it’s declared as such. Sort of. I’ve almost never encountered an interface where the documentation was so good that it wasn’t helpful to look at the implementation for further clarity.