kicad-developers team mailing list archive

["Brian F. G. Bidulock" <bidulock@xxxxxxxxxxx>]

Lorenzo,

On Fri, 25 Nov 2011, Lorenzo Marcantonio wrote:

> 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);

I hate to nip all that in the bud but you weren't listening.  There is
no place where a mask is called for.  The std::set would up being not
used at all except in some dialog code that I didn't want to convert.
Even there is is only used as a temporary.

A single (copper) layer board item exists only on one layer.  This is
represented within the board item (even before any changes) as a single
layer number.  A bit mask with one bit in it was created for this single
layer.  All multiple (copper) layer board items exist on a range of
layers (from n to n+m).  This is represented within the board item as a
codified layer number (4 bits for n, 4 bits for n+m).  PTH pad, a
special case, from (0) to (N-1).  This is represented within the pad
object as a bit mask with all copper layers set.  (Interestingly enough
the bit mask for all copper layers is only set when there is a hole,
even a zero diameter hole, through the pad, otherwise only a single
layer bit is set for SMD pads).  All non-copper items never had a bit
mask anyway: the layer on which they existed was determined by the layer
number only.

Now, no check was ever made whether a board item existed on multiple
disjoint layers, only whether it existed on one specific layer or
whether it existed somewhere between a range of layers.  So all bimask
bitwise AND operations (from outside the object), was replaced with a
set of comparison functions provided by board items inside the object.
A single layer object just checks whether its layer number matches the
comparison number or is within the comparison range.  This takes maybe
2 more nanoseconds than an bitwise AND.

To perform bitwise AND from legacy dialog code, I overloaded & on a mask
class (std::set inside but doesn't matter) and provided a class
conversion between a board item and a layer mask object.  Again, this
was only for legacy dialog code that I didn't want to convert and that
I did not have to touch by letting C++ do the conversions.

Understand that, for example, when a via is created, it is created with
a top and bottom layer number.  The existing layer mask inside the board
item has bits set between these two layers when it is created.  This is
only necessary because somebody decided to use bitwise AND operations
where they weren't necessary.  It is sufficient to compare the criteria
layer or range of layers to the layer or range of layers that the item
occupies.  No mask is called for.

Further, there is no need for any code outside the board item to even
know what the internal representation of layers is within the object.
It only needs the methods necessary to test certain things
(IsOnLayer(layer) and IsOnLayers(top,bot)).  By removing the layer mask
altogether, and exposing only virtual methods (or Interface as Vladmir
calls it), no code need know the internal representation of layers.
This accommodates 65,536 copper layers using 1 or 2 short integers,
saving space over the old method.  Using a bit array where is it not
called for would either require the use of 65,536 bit positions, or
would have to have two short integers to specify the valid range anyway.

Understand?

By the way, the layer classes that I provided are:

	Copper - copper layers of the board
	Dielectric - dielectric layers of the board
	Plating - plating applied to copper layers of the board
	HoleFile - hole filling primary process layers
	KeepOut - keep-out specifications for board layers
	ViaPlug - Via plugging (capping) layers
	SolderMask - solder mask (primary mask) layers
	Contacts - contacts (e.g. goldfinger) layers
	PeelMask - removable mask layers
	Finish - finish layers (e.g. NiAu, Ag, etc).
	SilkScreen - silk screen (legend) layers
	SolderPaste - solder paste layers
	Adhesive - adhesive layers
	Courtyard - courtyard specifications for board layers
	Component - component outlines for fabrication layers
	Coating - conformal coating layers
	Edges - board edges layers
	Eco - Engineering change order layers
	Probe - proble layers
	Fixture - fixture layers
	Comment - comment layers
	Drawing - fabrication and assembly drawing layers

I still need a couple more, such as seconday etch mask for embedded
resistors, (or a Resistance layer).  But seeing as there can be
65,536 classes, I don't think adding any layer will ever be a problem
again.

But my question was whether this should be later strapped in against
"testing" or "experimental".  I suppose "experimental".

--brian

-- 
Brian F. G. Bidulock    � The reasonable man adapts himself to the �
bidulock@xxxxxxxxxxx    � world; the unreasonable one persists in  �
http://www.openss7.org/ � trying  to adapt the  world  to himself. �
                        � Therefore  all  progress  depends on the �
                        � unreasonable man. -- George Bernard Shaw �