[thirdparty/glibc.git] / elf / dl-hwcaps.c

/* Hardware capability support for run-time dynamic loader.
   Copyright (C) 2012-2021 Free Software Foundation, Inc.
   This file is part of the GNU C Library.

   The GNU C Library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2.1 of the License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with the GNU C Library; if not, see
   <https://www.gnu.org/licenses/>.  */

#include <assert.h>
#include <elf.h>
#include <errno.h>
#include <libintl.h>
#include <unistd.h>
#include <ldsodefs.h>

#include <dl-procinfo.h>
#include <dl-hwcaps.h>

/* This is the result of counting the substrings in a colon-separated
   hwcaps string.  */
struct hwcaps_counts
{
  /* Number of substrings.  */
  size_t count;

  /* Sum of the individual substring lengths (without separators or
     null terminators).  */
  size_t total_length;

  /* Maximum length of an individual substring.  */
  size_t maximum_length;
};

/* Update *COUNTS according to the contents of HWCAPS.  Skip over
   entries whose bit is not set in MASK.  */
static void
update_hwcaps_counts (struct hwcaps_counts *counts, const char *hwcaps,
		      uint32_t bitmask, const char *mask)
{
  struct dl_hwcaps_split_masked sp;
  _dl_hwcaps_split_masked_init (&sp, hwcaps, bitmask, mask);
  while (_dl_hwcaps_split_masked (&sp))
    {
      ++counts->count;
      counts->total_length += sp.split.length;
      if (sp.split.length > counts->maximum_length)
	counts->maximum_length = sp.split.length;
    }
}

/* State for copy_hwcaps.  Must be initialized to point to
   the storage areas for the array and the strings themselves.  */
struct copy_hwcaps
{
  struct r_strlenpair *next_pair;
  char *next_string;
};

/* Copy HWCAPS into the string pairs and strings, advancing *TARGET.
   Skip over entries whose bit is not set in MASK.  */
static void
copy_hwcaps (struct copy_hwcaps *target, const char *hwcaps,
	     uint32_t bitmask, const char *mask)
{
  struct dl_hwcaps_split_masked sp;
  _dl_hwcaps_split_masked_init (&sp, hwcaps, bitmask, mask);
  while (_dl_hwcaps_split_masked (&sp))
    {
      target->next_pair->str = target->next_string;
      char *slash = __mempcpy (__mempcpy (target->next_string,
					  GLIBC_HWCAPS_PREFIX,
					  strlen (GLIBC_HWCAPS_PREFIX)),
			       sp.split.segment, sp.split.length);
      *slash = '/';
      target->next_pair->len
	= strlen (GLIBC_HWCAPS_PREFIX) + sp.split.length + 1;
      ++target->next_pair;
      target->next_string = slash + 1;
    }
}

struct dl_hwcaps_priority *_dl_hwcaps_priorities;
uint32_t _dl_hwcaps_priorities_length;

/* Allocate _dl_hwcaps_priorities and fill it with data.  */
static void
compute_priorities (size_t total_count, const char *prepend,
		    uint32_t bitmask, const char *mask)
{
  _dl_hwcaps_priorities = malloc (total_count
				  * sizeof (*_dl_hwcaps_priorities));
  if (_dl_hwcaps_priorities == NULL)
    _dl_signal_error (ENOMEM, NULL, NULL,
		      N_("cannot create HWCAP priorities"));
  _dl_hwcaps_priorities_length = total_count;

  /* First the prepended subdirectories.  */
  size_t i = 0;
  {
    struct dl_hwcaps_split sp;
    _dl_hwcaps_split_init (&sp, prepend);
    while (_dl_hwcaps_split (&sp))
      {
	_dl_hwcaps_priorities[i].name = sp.segment;
	_dl_hwcaps_priorities[i].name_length = sp.length;
	_dl_hwcaps_priorities[i].priority = i + 1;
	++i;
      }
  }

  /* Then the built-in subdirectories that are actually active.  */
  {
    struct dl_hwcaps_split_masked sp;
    _dl_hwcaps_split_masked_init (&sp, _dl_hwcaps_subdirs, bitmask, mask);
    while (_dl_hwcaps_split_masked (&sp))
      {
	_dl_hwcaps_priorities[i].name = sp.split.segment;
	_dl_hwcaps_priorities[i].name_length = sp.split.length;
	_dl_hwcaps_priorities[i].priority = i + 1;
	++i;
      }
  }
  assert (i == total_count);
}

/* Sort the _dl_hwcaps_priorities array by name.  */
static void
sort_priorities_by_name (void)
{
  /* Insertion sort.  There is no need to link qsort into the dynamic
     loader for such a short array.  */
  for (size_t i = 1; i < _dl_hwcaps_priorities_length; ++i)
    for (size_t j = i; j > 0; --j)
      {
	struct dl_hwcaps_priority *previous = _dl_hwcaps_priorities + j - 1;
	struct dl_hwcaps_priority *current = _dl_hwcaps_priorities + j;

	/* Bail out if current is greater or equal to the previous
	   value.  */
	uint32_t to_compare;
	if (current->name_length < previous->name_length)
	  to_compare = current->name_length;
	else
	  to_compare = previous->name_length;
	int cmp = memcmp (current->name, previous->name, to_compare);
	if (cmp > 0
	    || (cmp == 0 && current->name_length >= previous->name_length))
	  break;

	/* Swap *previous and *current.  */
	struct dl_hwcaps_priority tmp = *previous;
	*previous = *current;
	*current = tmp;
      }
}

/* Return an array of useful/necessary hardware capability names.  */
const struct r_strlenpair *
_dl_important_hwcaps (const char *glibc_hwcaps_prepend,
		      const char *glibc_hwcaps_mask,
		      size_t *sz, size_t *max_capstrlen)
{
  uint64_t hwcap_mask = GET_HWCAP_MASK();
  /* Determine how many important bits are set.  */
  uint64_t masked = GLRO(dl_hwcap) & hwcap_mask;
  size_t cnt = GLRO (dl_platform) != NULL;
  size_t n, m;
  struct r_strlenpair *result;
  struct r_strlenpair *rp;
  char *cp;

  /* glibc-hwcaps subdirectories.  These are exempted from the power
     set construction below.  */
  uint32_t hwcaps_subdirs_active = _dl_hwcaps_subdirs_active ();
  struct hwcaps_counts hwcaps_counts =  { 0, };
  update_hwcaps_counts (&hwcaps_counts, glibc_hwcaps_prepend, -1, NULL);
  update_hwcaps_counts (&hwcaps_counts, _dl_hwcaps_subdirs,
			hwcaps_subdirs_active, glibc_hwcaps_mask);
  compute_priorities (hwcaps_counts.count, glibc_hwcaps_prepend,
		      hwcaps_subdirs_active, glibc_hwcaps_mask);
  sort_priorities_by_name ();

  /* Each hwcaps subdirectory has a GLIBC_HWCAPS_PREFIX string prefix
     and a "/" suffix once stored in the result.  */
  hwcaps_counts.maximum_length += strlen (GLIBC_HWCAPS_PREFIX) + 1;
  size_t total = (hwcaps_counts.count * (strlen (GLIBC_HWCAPS_PREFIX) + 1)
		  + hwcaps_counts.total_length);

  /* Count the number of bits set in the masked value.  */
  for (n = 0; (~((1ULL << n) - 1) & masked) != 0; ++n)
    if ((masked & (1ULL << n)) != 0)
      ++cnt;

  /* For TLS enabled builds always add 'tls'.  */
  ++cnt;

  /* Create temporary data structure to generate result table.  */
  struct r_strlenpair temp[cnt];
  m = 0;
  for (n = 0; masked != 0; ++n)
    if ((masked & (1ULL << n)) != 0)
      {
	temp[m].str = _dl_hwcap_string (n);
	temp[m].len = strlen (temp[m].str);
	masked ^= 1ULL << n;
	++m;
      }
  if (GLRO (dl_platform) != NULL)
    {
      temp[m].str = GLRO (dl_platform);
      temp[m].len = GLRO (dl_platformlen);
      ++m;
    }

  temp[m].str = "tls";
  temp[m].len = 3;
  ++m;

  assert (m == cnt);

  /* Determine the total size of all strings together.  */
  if (cnt == 1)
    total += temp[0].len + 1;
  else
    {
      total += temp[0].len + temp[cnt - 1].len + 2;
      if (cnt > 2)
	{
	  total <<= 1;
	  for (n = 1; n + 1 < cnt; ++n)
	    total += temp[n].len + 1;
	  if (cnt > 3
	      && (cnt >= sizeof (size_t) * 8
		  || total + (sizeof (*result) << 3)
		     >= (1UL << (sizeof (size_t) * 8 - cnt + 3))))
	    _dl_signal_error (ENOMEM, NULL, NULL,
			      N_("cannot create capability list"));

	  total <<= cnt - 3;
	}
    }

  *sz = hwcaps_counts.count + (1 << cnt);

  /* This is the overall result, including both glibc-hwcaps
     subdirectories and the legacy hwcaps subdirectories using the
     power set construction.  */
  struct r_strlenpair *overall_result
    = malloc (*sz * sizeof (*result) + total);
  if (overall_result == NULL)
    _dl_signal_error (ENOMEM, NULL, NULL,
		      N_("cannot create capability list"));

  /* Fill in the glibc-hwcaps subdirectories.  */
  {
    struct copy_hwcaps target;
    target.next_pair = overall_result;
    target.next_string = (char *) (overall_result + *sz);
    copy_hwcaps (&target, glibc_hwcaps_prepend, -1, NULL);
    copy_hwcaps (&target, _dl_hwcaps_subdirs,
		 hwcaps_subdirs_active, glibc_hwcaps_mask);
    /* Set up the write target for the power set construction.  */
    result = target.next_pair;
    cp = target.next_string;
  }


  /* Power set construction begins here.  We use a very compressed way
     to store the various combinations of capability names.  */

  if (cnt == 1)
    {
      result[0].str = cp;
      result[0].len = temp[0].len + 1;
      result[1].str = cp;
      result[1].len = 0;
      cp = __mempcpy (cp, temp[0].str, temp[0].len);
      *cp = '/';
      if (result[0].len > hwcaps_counts.maximum_length)
	*max_capstrlen = result[0].len;
      else
	*max_capstrlen = hwcaps_counts.maximum_length;

      return overall_result;
    }

  /* Fill in the information.  This follows the following scheme
     (indices from TEMP for four strings):
	entry #0: 0, 1, 2, 3	binary: 1111
	      #1: 0, 1, 3		1101
	      #2: 0, 2, 3		1011
	      #3: 0, 3			1001
     This allows the representation of all possible combinations of
     capability names in the string.  First generate the strings.  */
  result[1].str = result[0].str = cp;
#define add(idx) \
      cp = __mempcpy (__mempcpy (cp, temp[idx].str, temp[idx].len), "/", 1);
  if (cnt == 2)
    {
      add (1);
      add (0);
    }
  else
    {
      n = 1 << (cnt - 1);
      do
	{
	  n -= 2;

	  /* We always add the last string.  */
	  add (cnt - 1);

	  /* Add the strings which have the bit set in N.  */
	  for (m = cnt - 2; m > 0; --m)
	    if ((n & (1 << m)) != 0)
	      add (m);

	  /* Always add the first string.  */
	  add (0);
	}
      while (n != 0);
    }
#undef add

  /* Now we are ready to install the string pointers and length.  */
  for (n = 0; n < (1UL << cnt); ++n)
    result[n].len = 0;
  n = cnt;
  do
    {
      size_t mask = 1 << --n;

      rp = result;
      for (m = 1 << cnt; m > 0; ++rp)
	if ((--m & mask) != 0)
	  rp->len += temp[n].len + 1;
    }
  while (n != 0);

  /* The first half of the strings all include the first string.  */
  n = (1 << cnt) - 2;
  rp = &result[2];
  while (n != (1UL << (cnt - 1)))
    {
      if ((--n & 1) != 0)
	rp[0].str = rp[-2].str + rp[-2].len;
      else
	rp[0].str = rp[-1].str;
      ++rp;
    }

  /* The second half starts right after the first part of the string of
     the corresponding entry in the first half.  */
  do
    {
      rp[0].str = rp[-(1 << (cnt - 1))].str + temp[cnt - 1].len + 1;
      ++rp;
    }
  while (--n != 0);

  /* The maximum string length.  */
  if (result[0].len > hwcaps_counts.maximum_length)
    *max_capstrlen = result[0].len;
  else
    *max_capstrlen = hwcaps_counts.maximum_length;

  return overall_result;
}
Commit	Line	Data
53cea63e	1	/* Hardware capability support for run-time dynamic loader.
2b778ceb	2	Copyright (C) 2012-2021 Free Software Foundation, Inc.
53cea63e L	3	This file is part of the GNU C Library.
	4
	5	The GNU C Library is free software; you can redistribute it and/or
	6	modify it under the terms of the GNU Lesser General Public
	7	License as published by the Free Software Foundation; either
	8	version 2.1 of the License, or (at your option) any later version.
	9
	10	The GNU C Library is distributed in the hope that it will be useful,
	11	but WITHOUT ANY WARRANTY; without even the implied warranty of
	12	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	13	Lesser General Public License for more details.
	14
	15	You should have received a copy of the GNU Lesser General Public
	16	License along with the GNU C Library; if not, see
5a82c748	17	<https://www.gnu.org/licenses/>. */
53cea63e L	18
	19	#include <assert.h>
	20	#include <elf.h>
	21	#include <errno.h>
	22	#include <libintl.h>
	23	#include <unistd.h>
	24	#include <ldsodefs.h>
	25
	26	#include <dl-procinfo.h>
ff08fc59	27	#include <dl-hwcaps.h>
53cea63e	28
dad90d52 FW	29	/* This is the result of counting the substrings in a colon-separated
	30	hwcaps string. */
	31	struct hwcaps_counts
	32	{
	33	/* Number of substrings. */
	34	size_t count;
	35
	36	/* Sum of the individual substring lengths (without separators or
	37	null terminators). */
	38	size_t total_length;
	39
	40	/* Maximum length of an individual substring. */
	41	size_t maximum_length;
	42	};
	43
	44	/* Update *COUNTS according to the contents of HWCAPS. Skip over
	45	entries whose bit is not set in MASK. */
	46	static void
	47	update_hwcaps_counts (struct hwcaps_counts counts, const char hwcaps,
	48	uint32_t bitmask, const char *mask)
	49	{
	50	struct dl_hwcaps_split_masked sp;
	51	_dl_hwcaps_split_masked_init (&sp, hwcaps, bitmask, mask);
	52	while (_dl_hwcaps_split_masked (&sp))
	53	{
	54	++counts->count;
	55	counts->total_length += sp.split.length;
	56	if (sp.split.length > counts->maximum_length)
	57	counts->maximum_length = sp.split.length;
	58	}
	59	}
	60
	61	/* State for copy_hwcaps. Must be initialized to point to
	62	the storage areas for the array and the strings themselves. */
	63	struct copy_hwcaps
	64	{
	65	struct r_strlenpair *next_pair;
	66	char *next_string;
	67	};
	68
	69	/* Copy HWCAPS into the string pairs and strings, advancing *TARGET.
	70	Skip over entries whose bit is not set in MASK. */
	71	static void
	72	copy_hwcaps (struct copy_hwcaps target, const char hwcaps,
	73	uint32_t bitmask, const char *mask)
	74	{
	75	struct dl_hwcaps_split_masked sp;
	76	_dl_hwcaps_split_masked_init (&sp, hwcaps, bitmask, mask);
	77	while (_dl_hwcaps_split_masked (&sp))
	78	{
	79	target->next_pair->str = target->next_string;
	80	char *slash = __mempcpy (__mempcpy (target->next_string,
	81	GLIBC_HWCAPS_PREFIX,
	82	strlen (GLIBC_HWCAPS_PREFIX)),
	83	sp.split.segment, sp.split.length);
	84	*slash = '/';
	85	target->next_pair->len
	86	= strlen (GLIBC_HWCAPS_PREFIX) + sp.split.length + 1;
	87	++target->next_pair;
	88	target->next_string = slash + 1;
	89	}
	90	}
	91
600d9e0c FW	92	struct dl_hwcaps_priority *_dl_hwcaps_priorities;
	93	uint32_t _dl_hwcaps_priorities_length;
	94
	95	/* Allocate _dl_hwcaps_priorities and fill it with data. */
	96	static void
	97	compute_priorities (size_t total_count, const char *prepend,
	98	uint32_t bitmask, const char *mask)
	99	{
	100	_dl_hwcaps_priorities = malloc (total_count
	101	* sizeof (*_dl_hwcaps_priorities));
	102	if (_dl_hwcaps_priorities == NULL)
	103	_dl_signal_error (ENOMEM, NULL, NULL,
	104	N_("cannot create HWCAP priorities"));
	105	_dl_hwcaps_priorities_length = total_count;
	106
	107	/* First the prepended subdirectories. */
	108	size_t i = 0;
	109	{
	110	struct dl_hwcaps_split sp;
	111	_dl_hwcaps_split_init (&sp, prepend);
	112	while (_dl_hwcaps_split (&sp))
	113	{
	114	_dl_hwcaps_priorities[i].name = sp.segment;
	115	_dl_hwcaps_priorities[i].name_length = sp.length;
	116	_dl_hwcaps_priorities[i].priority = i + 1;
	117	++i;
	118	}
	119	}
	120
	121	/* Then the built-in subdirectories that are actually active. */
	122	{
	123	struct dl_hwcaps_split_masked sp;
	124	_dl_hwcaps_split_masked_init (&sp, _dl_hwcaps_subdirs, bitmask, mask);
	125	while (_dl_hwcaps_split_masked (&sp))
	126	{
	127	_dl_hwcaps_priorities[i].name = sp.split.segment;
	128	_dl_hwcaps_priorities[i].name_length = sp.split.length;
	129	_dl_hwcaps_priorities[i].priority = i + 1;
	130	++i;
	131	}
	132	}
	133	assert (i == total_count);
	134	}
	135
	136	/* Sort the _dl_hwcaps_priorities array by name. */
	137	static void
	138	sort_priorities_by_name (void)
	139	{
	140	/* Insertion sort. There is no need to link qsort into the dynamic
	141	loader for such a short array. */
	142	for (size_t i = 1; i < _dl_hwcaps_priorities_length; ++i)
	143	for (size_t j = i; j > 0; --j)
	144	{
	145	struct dl_hwcaps_priority *previous = _dl_hwcaps_priorities + j - 1;
	146	struct dl_hwcaps_priority *current = _dl_hwcaps_priorities + j;
	147
	148	/* Bail out if current is greater or equal to the previous
	149	value. */
	150	uint32_t to_compare;
	151	if (current->name_length < previous->name_length)
	152	to_compare = current->name_length;
	153	else
	154	to_compare = previous->name_length;
	155	int cmp = memcmp (current->name, previous->name, to_compare);
0d4ed9d4	156	if (cmp > 0
600d9e0c FW	157	\|\| (cmp == 0 && current->name_length >= previous->name_length))
	158	break;
	159
	160	/* Swap previous and current. */
	161	struct dl_hwcaps_priority tmp = *previous;
	162	previous = current;
	163	*current = tmp;
	164	}
	165	}
	166
53cea63e L	167	/* Return an array of useful/necessary hardware capability names. */
53cea63e L	168	const struct r_strlenpair *
dad90d52 FW	169	_dl_important_hwcaps (const char *glibc_hwcaps_prepend,
	170	const char *glibc_hwcaps_mask,
	171	size_t sz, size_t max_capstrlen)
53cea63e	172	{
ff08fc59	173	uint64_t hwcap_mask = GET_HWCAP_MASK();
53cea63e	174	/* Determine how many important bits are set. */
ff08fc59	175	uint64_t masked = GLRO(dl_hwcap) & hwcap_mask;
bb5fd5ce	176	size_t cnt = GLRO (dl_platform) != NULL;
53cea63e	177	size_t n, m;
53cea63e L	178	struct r_strlenpair *result;
	179	struct r_strlenpair *rp;
	180	char *cp;
	181
dad90d52 FW	182	/* glibc-hwcaps subdirectories. These are exempted from the power
	183	set construction below. */
	184	uint32_t hwcaps_subdirs_active = _dl_hwcaps_subdirs_active ();
	185	struct hwcaps_counts hwcaps_counts = { 0, };
	186	update_hwcaps_counts (&hwcaps_counts, glibc_hwcaps_prepend, -1, NULL);
	187	update_hwcaps_counts (&hwcaps_counts, _dl_hwcaps_subdirs,
	188	hwcaps_subdirs_active, glibc_hwcaps_mask);
600d9e0c FW	189	compute_priorities (hwcaps_counts.count, glibc_hwcaps_prepend,
	190	hwcaps_subdirs_active, glibc_hwcaps_mask);
	191	sort_priorities_by_name ();
dad90d52 FW	192
	193	/* Each hwcaps subdirectory has a GLIBC_HWCAPS_PREFIX string prefix
	194	and a "/" suffix once stored in the result. */
8a30bb4e	195	hwcaps_counts.maximum_length += strlen (GLIBC_HWCAPS_PREFIX) + 1;
dad90d52 FW	196	size_t total = (hwcaps_counts.count * (strlen (GLIBC_HWCAPS_PREFIX) + 1)
	197	+ hwcaps_counts.total_length);
	198
53cea63e L	199	/* Count the number of bits set in the masked value. */
	200	for (n = 0; (~((1ULL << n) - 1) & masked) != 0; ++n)
	201	if ((masked & (1ULL << n)) != 0)
	202	++cnt;
	203
53cea63e L	204	/* For TLS enabled builds always add 'tls'. */
	205	++cnt;
	206
	207	/* Create temporary data structure to generate result table. */
573c29b2	208	struct r_strlenpair temp[cnt];
53cea63e	209	m = 0;
53cea63e L	210	for (n = 0; masked != 0; ++n)
	211	if ((masked & (1ULL << n)) != 0)
	212	{
	213	temp[m].str = _dl_hwcap_string (n);
	214	temp[m].len = strlen (temp[m].str);
	215	masked ^= 1ULL << n;
	216	++m;
	217	}
bb5fd5ce	218	if (GLRO (dl_platform) != NULL)
53cea63e	219	{
bb5fd5ce FW	220	temp[m].str = GLRO (dl_platform);
bb5fd5ce FW	221	temp[m].len = GLRO (dl_platformlen);
53cea63e L	222	++m;
	223	}
	224
	225	temp[m].str = "tls";
	226	temp[m].len = 3;
	227	++m;
	228
	229	assert (m == cnt);
	230
	231	/* Determine the total size of all strings together. */
	232	if (cnt == 1)
dad90d52	233	total += temp[0].len + 1;
53cea63e L	234	else
53cea63e L	235	{
dad90d52	236	total += temp[0].len + temp[cnt - 1].len + 2;
53cea63e L	237	if (cnt > 2)
	238	{
	239	total <<= 1;
	240	for (n = 1; n + 1 < cnt; ++n)
	241	total += temp[n].len + 1;
	242	if (cnt > 3
	243	&& (cnt >= sizeof (size_t) * 8
	244	\|\| total + (sizeof (*result) << 3)
	245	>= (1UL << (sizeof (size_t) * 8 - cnt + 3))))
	246	_dl_signal_error (ENOMEM, NULL, NULL,
	247	N_("cannot create capability list"));
	248
	249	total <<= cnt - 3;
	250	}
	251	}
	252
dad90d52 FW	253	*sz = hwcaps_counts.count + (1 << cnt);
	254
	255	/* This is the overall result, including both glibc-hwcaps
	256	subdirectories and the legacy hwcaps subdirectories using the
	257	power set construction. */
	258	struct r_strlenpair *overall_result
	259	= malloc (sz sizeof (*result) + total);
	260	if (overall_result == NULL)
53cea63e L	261	_dl_signal_error (ENOMEM, NULL, NULL,
	262	N_("cannot create capability list"));
	263
dad90d52 FW	264	/* Fill in the glibc-hwcaps subdirectories. */
	265	{
	266	struct copy_hwcaps target;
	267	target.next_pair = overall_result;
	268	target.next_string = (char ) (overall_result + sz);
	269	copy_hwcaps (&target, glibc_hwcaps_prepend, -1, NULL);
	270	copy_hwcaps (&target, _dl_hwcaps_subdirs,
	271	hwcaps_subdirs_active, glibc_hwcaps_mask);
	272	/* Set up the write target for the power set construction. */
	273	result = target.next_pair;
	274	cp = target.next_string;
	275	}
	276
	277
	278	/* Power set construction begins here. We use a very compressed way
	279	to store the various combinations of capability names. */
	280
53cea63e L	281	if (cnt == 1)
53cea63e L	282	{
dad90d52	283	result[0].str = cp;
53cea63e	284	result[0].len = temp[0].len + 1;
dad90d52	285	result[1].str = cp;
53cea63e	286	result[1].len = 0;
dad90d52	287	cp = __mempcpy (cp, temp[0].str, temp[0].len);
53cea63e	288	*cp = '/';
dad90d52 FW	289	if (result[0].len > hwcaps_counts.maximum_length)
	290	*max_capstrlen = result[0].len;
	291	else
	292	*max_capstrlen = hwcaps_counts.maximum_length;
53cea63e	293
dad90d52	294	return overall_result;
53cea63e L	295	}
	296
	297	/* Fill in the information. This follows the following scheme
573c29b2	298	(indices from TEMP for four strings):
53cea63e L	299	entry #0: 0, 1, 2, 3 binary: 1111
	300	#1: 0, 1, 3 1101
	301	#2: 0, 2, 3 1011
	302	#3: 0, 3 1001
	303	This allows the representation of all possible combinations of
	304	capability names in the string. First generate the strings. */
dad90d52	305	result[1].str = result[0].str = cp;
53cea63e L	306	#define add(idx) \
	307	cp = __mempcpy (__mempcpy (cp, temp[idx].str, temp[idx].len), "/", 1);
	308	if (cnt == 2)
	309	{
	310	add (1);
	311	add (0);
	312	}
	313	else
	314	{
	315	n = 1 << (cnt - 1);
	316	do
	317	{
	318	n -= 2;
	319
	320	/* We always add the last string. */
	321	add (cnt - 1);
	322
	323	/* Add the strings which have the bit set in N. */
	324	for (m = cnt - 2; m > 0; --m)
	325	if ((n & (1 << m)) != 0)
	326	add (m);
	327
	328	/* Always add the first string. */
	329	add (0);
	330	}
	331	while (n != 0);
	332	}
	333	#undef add
	334
	335	/* Now we are ready to install the string pointers and length. */
	336	for (n = 0; n < (1UL << cnt); ++n)
	337	result[n].len = 0;
	338	n = cnt;
	339	do
	340	{
	341	size_t mask = 1 << --n;
	342
	343	rp = result;
	344	for (m = 1 << cnt; m > 0; ++rp)
	345	if ((--m & mask) != 0)
	346	rp->len += temp[n].len + 1;
	347	}
	348	while (n != 0);
	349
	350	/* The first half of the strings all include the first string. */
	351	n = (1 << cnt) - 2;
	352	rp = &result[2];
	353	while (n != (1UL << (cnt - 1)))
	354	{
	355	if ((--n & 1) != 0)
	356	rp[0].str = rp[-2].str + rp[-2].len;
	357	else
	358	rp[0].str = rp[-1].str;
	359	++rp;
	360	}
	361
	362	/* The second half starts right after the first part of the string of
	363	the corresponding entry in the first half. */
	364	do
	365	{
	366	rp[0].str = rp[-(1 << (cnt - 1))].str + temp[cnt - 1].len + 1;
	367	++rp;
	368	}
	369	while (--n != 0);
370
371	/* The maximum string length. */
dad90d52 FW	372	if (result[0].len > hwcaps_counts.maximum_length)
	373	*max_capstrlen = result[0].len;
	374	else
	375	*max_capstrlen = hwcaps_counts.maximum_length;
53cea63e	376
dad90d52	377	return overall_result;
53cea63e	378	}