kicad-developers team mailing list archive

[Lorenzo Marcantonio <l.marcantonio@xxxxxxxxxxxx>]

On Fri, Nov 25, 2011 at 10:33:29AM -0700, Brian F. G. Bidulock wrote:
> Well, in fact, almost all bitwise AND comparisons are either testing
> for a single layer or all copper layers.  Sometimes a range of layers
> (e.g. for buried or blind vias).  This is not a good use of a bit mask.
> They were all easily converted into a test for a single layer or a test
> for any layer within a layer class, or a layer within a range.
> 
> So, I implemented the stack layer mask as std::set but implemented a
> layer id and layer pair identifier as one or two 32-bit values broken
> into 16-bit layer class and 16-bit layer index.  I also described a
> set of abstract base classes for board items (LAYERABLE_ITEM, LAYER_ITEM, 
> LAYERED_ITEM, STACKED_ITEM, LAYERS_ITEM) to encapsulate layer behaviour
> inside the board item instead of outside it.  But you can find this info
> (and the rationale for changes) in the design document and in the code
> comments on my kicad-brian branch.

Isn't a std::set a little overweight for the layer mask? IIRC it's usually
implemented as a btree (red-black trees in g++), and there is one for each pad
at least in the board! A bitmasked int is a bit vector, which is a lot more
efficient both in size and space. Also a bitmask is the very essence of a
padstack (even if we do not handle them explicitly).

IMHO a better idea would be a bit vector for each primitive and a parallel
structure to define the stackup (another vector or something), which also
declare the layer ordering (needed for blind vias and maybe other things);

In my experience there are the following kind of layers in a PCB:

- The board edge (or border) --- mandatory, only one of them

- Solder mask: none, top, bottom or both of them

- Silk screen: none, top, bottom or both of them (silk is better handled
  differently than artworks layers, because is subject to DRC and masking);

- Copper layers: as many as we need but top and bottom are slightly different
  than the inner; some kind of association between them is needed to handle
  buried vias (i.e. declare what layers are on the same core)

- Other layers: drawing, assembly, glue, playground, comments, whatever;
  essentially artwork layer with no specific management. We need two kind of
  these: standalone and paired layers. Standalone is a simple layer, paired
  layer are associated to be flipped with the component (i.e. glue and
  playgrounds). This was a much requested feature.

- Solder paste *could* actually be handled as artwork but in practice I think
  is better to handle it as specific kind of layer; there could be specific DRC
  check for it (for example: paste without solder mask!) but otherwise is an
  artwork layer like others.

These are the layers seen from the 'board' side; from the 'library' side there
are some specific issues:

- Pads on copper layers need to be declared as 'no copper', 'top only', 'bottom
  only', or 'through hole' (i.e. all copper layers); we could call this 'copper
  policy', and it's a pad attribute saved in the library;

- There could be a mismatch between library definition and the current board
  when instancing a component. For example you could have a lib with glue but
  no glue layer on the current board. What do we do in this case? do we
  instance the module without glue or ensure the required layers are present in
  the board?

- As a consequence of the previous two items, the pads needs to be 'expanded'
  to handle all the layers on the board (i.e. a TH pad should be added to all
  the copper layer in the board);

It important that the pad presence on the layer is actually 'exploded' (i.e.
not only implicit from the copper policy) because in the inner layer for
fabrication and space reasons the copper pad is actually excluded (these are
usually called 'isolated pad'); that would be a good step toward a useful
padstack feature (we would need to enhance the clearance rule to handle
correctly this situation). *This* is the reason for which I call for a
bitmask:P

As for the data structure used for implementing this I agree that there are
pros and cons (as usual) between a set and a bit array...

- A set can use compound identifiers (like you layer type/layer number, which
  IMHO is actually a good idea; a better one would be store in the set directly
  the pointer to the layer descriptor), a bitarray is best handled with
  'compact' indexes. In this case the layer type would be looked up from the
  stackup structure;

- A set is bigger in memory: I don't remember the overhead of red-blacks but
  we're talking of more than 3 word for component (data, pointers and flags),
  unless is not stored as an heap (but IIRC red-blacks can't be stored as an
  heap... I don't remember, really, but clearly);

- A set is slower O(n log n) vs O(1) for every operation and involves compares;
  O(1) is difficult to beat, since a bit array has the same characteristics of
  direct hashing :D also a set is heavy on dynamic allocation (altough the STL
  has allocators to obviate for this, and our layer mask is read-mostly);

- If we had to handle *a lot* of layers (128 layers are only 4 word plus some
  fixed overhead in a bitarray), given that most entities are only on one layer
  the set could be an interesting idea; a devilish board could have maybe 50
  layers (but I doubt that you'd use pcbnew for *that* kind of
  manufacturing:P), and a long long keeps 64 layers in two words (that is,
  using a POD instead of a bitarray, that would make a ceiling on the total
  number of layers... *maybe* we don't want it). A bitarray could use about
  four words for it. (is the same tradeoff used for sparse matrices...)

- Actually the only things that can be on more than one layer are pads and
  vias! Am I wrong? Tracks are only on one layer and so are graphic entities;
  so the choice on the data structure is only needed for pad instances:P memory
  overhead is then of lower importance

So, at the end, we'll have an int indexing the layer (in a layer table
describing the stackup), an int in *most* entity classes, and some kind of set
implementation for pads. 

I think that the most common operation with layers is actually the predicate
'is this entity on this layer': this would be an int comparison (for most
entities) or (for vias and pads) a lookup on the layer set (little more than a
shift and and for the bit array, a tree traversal for the set)

The other operation you talked about ('is this entity on one of these layers'
where 'these'  is a range using a set or a mask using a bitarray) is in theory
a set intersection.

In a bitarray that's a logic and (IIRC std::bitset overload the & operator for
this), using an std::set you have a 'little' problem: you can only ask for a
specific value (with find()). Even if it's actually a sorted container, the
std::set interface doesn't handle range queries. You need to ask for each
single layer (and each query is a tree traversal). Even if the performance it
would be probably very low, IMHO is a sign that a set is not the right data
structure for this.

So I still think that a bitarray is a better container for this job than a tree
set... and anyway it's simpler! (as I said a long long would be *even* simpler
but would restrict to 64 layers total which *could* be a problem)

-- 
Lorenzo Marcantonio
Logos Srl