1255e72915d4cbddceb435e13d81601755714e9fSE Android 2255e72915d4cbddceb435e13d81601755714e9fSE Android/* Author : Stephen Smalley, <sds@epoch.ncsc.mil> */ 3255e72915d4cbddceb435e13d81601755714e9fSE Android 4255e72915d4cbddceb435e13d81601755714e9fSE Android/* FLASK */ 5255e72915d4cbddceb435e13d81601755714e9fSE Android 6255e72915d4cbddceb435e13d81601755714e9fSE Android/* 7255e72915d4cbddceb435e13d81601755714e9fSE Android * An extensible bitmap is a bitmap that supports an 8255e72915d4cbddceb435e13d81601755714e9fSE Android * arbitrary number of bits. Extensible bitmaps are 9255e72915d4cbddceb435e13d81601755714e9fSE Android * used to represent sets of values, such as types, 10255e72915d4cbddceb435e13d81601755714e9fSE Android * roles, categories, and classes. 11255e72915d4cbddceb435e13d81601755714e9fSE Android * 12255e72915d4cbddceb435e13d81601755714e9fSE Android * Each extensible bitmap is implemented as a linked 13255e72915d4cbddceb435e13d81601755714e9fSE Android * list of bitmap nodes, where each bitmap node has 14255e72915d4cbddceb435e13d81601755714e9fSE Android * an explicitly specified starting bit position within 15255e72915d4cbddceb435e13d81601755714e9fSE Android * the total bitmap. 16255e72915d4cbddceb435e13d81601755714e9fSE Android */ 17255e72915d4cbddceb435e13d81601755714e9fSE Android 18255e72915d4cbddceb435e13d81601755714e9fSE Android#ifndef _SEPOL_POLICYDB_EBITMAP_H_ 19255e72915d4cbddceb435e13d81601755714e9fSE Android#define _SEPOL_POLICYDB_EBITMAP_H_ 20255e72915d4cbddceb435e13d81601755714e9fSE Android 21255e72915d4cbddceb435e13d81601755714e9fSE Android#include <stdint.h> 22255e72915d4cbddceb435e13d81601755714e9fSE Android#include <string.h> 23255e72915d4cbddceb435e13d81601755714e9fSE Android 24255e72915d4cbddceb435e13d81601755714e9fSE Android#define MAPTYPE uint64_t /* portion of bitmap in each node */ 25255e72915d4cbddceb435e13d81601755714e9fSE Android#define MAPSIZE (sizeof(MAPTYPE) * 8) /* number of bits in node bitmap */ 26255e72915d4cbddceb435e13d81601755714e9fSE Android#define MAPBIT 1ULL /* a bit in the node bitmap */ 27255e72915d4cbddceb435e13d81601755714e9fSE Android 28255e72915d4cbddceb435e13d81601755714e9fSE Androidtypedef struct ebitmap_node { 29255e72915d4cbddceb435e13d81601755714e9fSE Android uint32_t startbit; /* starting position in the total bitmap */ 30255e72915d4cbddceb435e13d81601755714e9fSE Android MAPTYPE map; /* this node's portion of the bitmap */ 31255e72915d4cbddceb435e13d81601755714e9fSE Android struct ebitmap_node *next; 32255e72915d4cbddceb435e13d81601755714e9fSE Android} ebitmap_node_t; 33255e72915d4cbddceb435e13d81601755714e9fSE Android 34255e72915d4cbddceb435e13d81601755714e9fSE Androidtypedef struct ebitmap { 35255e72915d4cbddceb435e13d81601755714e9fSE Android ebitmap_node_t *node; /* first node in the bitmap */ 36255e72915d4cbddceb435e13d81601755714e9fSE Android uint32_t highbit; /* highest position in the total bitmap */ 37255e72915d4cbddceb435e13d81601755714e9fSE Android} ebitmap_t; 38255e72915d4cbddceb435e13d81601755714e9fSE Android 39255e72915d4cbddceb435e13d81601755714e9fSE Android#define ebitmap_length(e) ((e)->highbit) 40255e72915d4cbddceb435e13d81601755714e9fSE Android#define ebitmap_startbit(e) ((e)->node ? (e)->node->startbit : 0) 41255e72915d4cbddceb435e13d81601755714e9fSE Android#define ebitmap_startnode(e) ((e)->node) 42255e72915d4cbddceb435e13d81601755714e9fSE Android 43255e72915d4cbddceb435e13d81601755714e9fSE Androidstatic inline unsigned int ebitmap_start(const ebitmap_t * e, 44255e72915d4cbddceb435e13d81601755714e9fSE Android ebitmap_node_t ** n) 45255e72915d4cbddceb435e13d81601755714e9fSE Android{ 46255e72915d4cbddceb435e13d81601755714e9fSE Android 47255e72915d4cbddceb435e13d81601755714e9fSE Android *n = e->node; 48255e72915d4cbddceb435e13d81601755714e9fSE Android return ebitmap_startbit(e); 49255e72915d4cbddceb435e13d81601755714e9fSE Android} 50255e72915d4cbddceb435e13d81601755714e9fSE Android 51255e72915d4cbddceb435e13d81601755714e9fSE Androidstatic inline void ebitmap_init(ebitmap_t * e) 52255e72915d4cbddceb435e13d81601755714e9fSE Android{ 53255e72915d4cbddceb435e13d81601755714e9fSE Android memset(e, 0, sizeof(*e)); 54255e72915d4cbddceb435e13d81601755714e9fSE Android} 55255e72915d4cbddceb435e13d81601755714e9fSE Android 56255e72915d4cbddceb435e13d81601755714e9fSE Androidstatic inline unsigned int ebitmap_next(ebitmap_node_t ** n, unsigned int bit) 57255e72915d4cbddceb435e13d81601755714e9fSE Android{ 58255e72915d4cbddceb435e13d81601755714e9fSE Android if ((bit == ((*n)->startbit + MAPSIZE - 1)) && (*n)->next) { 59255e72915d4cbddceb435e13d81601755714e9fSE Android *n = (*n)->next; 60255e72915d4cbddceb435e13d81601755714e9fSE Android return (*n)->startbit; 61255e72915d4cbddceb435e13d81601755714e9fSE Android } 62255e72915d4cbddceb435e13d81601755714e9fSE Android 63255e72915d4cbddceb435e13d81601755714e9fSE Android return (bit + 1); 64255e72915d4cbddceb435e13d81601755714e9fSE Android} 65255e72915d4cbddceb435e13d81601755714e9fSE Android 66255e72915d4cbddceb435e13d81601755714e9fSE Androidstatic inline int ebitmap_node_get_bit(ebitmap_node_t * n, unsigned int bit) 67255e72915d4cbddceb435e13d81601755714e9fSE Android{ 68255e72915d4cbddceb435e13d81601755714e9fSE Android if (n->map & (MAPBIT << (bit - n->startbit))) 69255e72915d4cbddceb435e13d81601755714e9fSE Android return 1; 70255e72915d4cbddceb435e13d81601755714e9fSE Android return 0; 71255e72915d4cbddceb435e13d81601755714e9fSE Android} 72255e72915d4cbddceb435e13d81601755714e9fSE Android 73255e72915d4cbddceb435e13d81601755714e9fSE Android#define ebitmap_for_each_bit(e, n, bit) \ 74255e72915d4cbddceb435e13d81601755714e9fSE Android for (bit = ebitmap_start(e, &n); bit < ebitmap_length(e); bit = ebitmap_next(&n, bit)) \ 75255e72915d4cbddceb435e13d81601755714e9fSE Android 76255e72915d4cbddceb435e13d81601755714e9fSE Androidextern int ebitmap_cmp(const ebitmap_t * e1, const ebitmap_t * e2); 77255e72915d4cbddceb435e13d81601755714e9fSE Androidextern int ebitmap_or(ebitmap_t * dst, const ebitmap_t * e1, const ebitmap_t * e2); 78255e72915d4cbddceb435e13d81601755714e9fSE Androidextern int ebitmap_union(ebitmap_t * dst, const ebitmap_t * e1); 79fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalleyextern int ebitmap_and(ebitmap_t *dst, ebitmap_t *e1, ebitmap_t *e2); 80fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalleyextern int ebitmap_xor(ebitmap_t *dst, ebitmap_t *e1, ebitmap_t *e2); 81fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalleyextern int ebitmap_not(ebitmap_t *dst, ebitmap_t *e1, unsigned int maxbit); 82fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalleyextern int ebitmap_andnot(ebitmap_t *dst, ebitmap_t *e1, ebitmap_t *e2, unsigned int maxbit); 83fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalleyextern unsigned int ebitmap_cardinality(ebitmap_t *e1); 84fb82f8ed213dd54eebc6bdd5557984c3ba870496Stephen Smalleyextern int ebitmap_hamming_distance(ebitmap_t * e1, ebitmap_t * e2); 85255e72915d4cbddceb435e13d81601755714e9fSE Androidextern int ebitmap_cpy(ebitmap_t * dst, const ebitmap_t * src); 86255e72915d4cbddceb435e13d81601755714e9fSE Androidextern int ebitmap_contains(const ebitmap_t * e1, const ebitmap_t * e2); 87255e72915d4cbddceb435e13d81601755714e9fSE Androidextern int ebitmap_get_bit(const ebitmap_t * e, unsigned int bit); 88255e72915d4cbddceb435e13d81601755714e9fSE Androidextern int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value); 89255e72915d4cbddceb435e13d81601755714e9fSE Androidextern void ebitmap_destroy(ebitmap_t * e); 90255e72915d4cbddceb435e13d81601755714e9fSE Androidextern int ebitmap_read(ebitmap_t * e, void *fp); 91255e72915d4cbddceb435e13d81601755714e9fSE Android 92255e72915d4cbddceb435e13d81601755714e9fSE Android#endif /* _EBITMAP_H_ */ 93255e72915d4cbddceb435e13d81601755714e9fSE Android 94255e72915d4cbddceb435e13d81601755714e9fSE Android/* FLASK */ 95